Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Data Structure - Sorting Techniques
By arranging the data in a specific order, it is sorted
...

The most typical orderings are lexical or numerical
...
Data may be
presented in more comprehensible ways by sorting
...

• Dictionary − The dictionary stores words in an
alphabetical order so that searching of any word
becomes easy
...

These algorithms are said to sort "in-place," or for example,
inside the boundaries of the array itself, and they are said to
consume less space
...
The
bubble sort is an instance of in-place sorting
...
Sorting with a space need of equal to or
higher than zero is known as not-in-place sorting
...


Stable and Not Stable Sorting
If a sorting algorithm, after sorting the contents, does not change
the sequence of similar content in which they appear, it is
called stable sorting
...


Stability of an algorithm matters when we wish to maintain the
sequence of original elements, like in a tuple for example
...
As a result, adaptive algorithms will aim to avoid

reordering elements that are already sorted in the source list
while sorting
...
To ensure that the elements
are properly sorted, they attempt to force each one to be
reordered
...
For
example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next
element is greater than the previous element
...
For example, 9,
8, 6, 4, 3, 1 are in decreasing order, as every next element is less
than the previous element
...
This order occurs when the sequence contains
duplicate values
...


Non-Decreasing Order
If each element in a sequence of values is bigger than or equal to
the one before it, the sequence is said to be in non-decreasing
order
...
For instance, the elements 1, 3, 3, 6, and 8 are not in
decreasing order since each one is bigger than or equal to (in the
case of element 3) but not lower than the one before it
...
Each pair of
adjacent elements in this comparison-based sorting algorithm is
compared to each other, and if they are not in the correct order,
the elements are swapped
...

How Bubble Sort Works?
We take an unsorted array for our example
...


Bubble sort starts with very first two elements, comparing them
to check which one is greater
...
Next, we compare 33 with 27
...


The new array should look like this −

Next we compare 33 and 35
...


Then we move to the next two values, 35 and 10
...
Hence they are not sorted
...
We find that we have reached the end of
the array
...
After the second iteration, it should look like
this −

Notice that after each iteration, at least one value moves at the
end
...


Now we should look into some practical aspects of bubble sort
...
We further assume
that swap function swaps the values of the given array elements
...

This could lead to a few complexity difficulties, such as what if
the array does not require any further swapping because all of
the members are ascending
...
If no swap has
occurred, i
...
the array requires no more processing to be sorted,
it will come out of the loop
...
count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true

end if
end for
/*if no number was swapped that means
array is sorted now, break the loop
...
Consequently, the next iteration need not include
elements that have already been sorted
...

Data Structure and Algorithms Insertion Sort
This is an in-place comparison-based sorting algorithm
...
For example, the
lower part of an array is maintained to be sorted
...
Hence the
name, insertion sort
...
This
algorithm is not suitable for large data sets as its average and
worst case complexity are of Ο(n2), where n is the number of
items
...


Insertion sort compares the first two elements
...
For
now, 14 is in sorted sub-list
...


And finds that 33 is not in the correct position
...
It also checks with all the elements of sorted
sub-list
...
Hence, the sorted sub-list
remains sorted after swapping
...
Next, it
compares 33 with 10
...


So we swap them
...


Hence, we swap them too
...


We swap them again
...


This process goes on until all the unsorted values are covered in
a sorted sub-list
...

Algorithm
Now we have a bigger picture of how this sorting technique
works, so we can derive simple steps by which we can achieve
insertion sort
...
return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is
greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Pseudocode
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */

valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert
do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure

Data Structure and Algorithms Selection Sort
Selection sort is a simple sorting algorithm
...
Initially, the sorted part
is empty and the unsorted part is the entire list
...
This process continues moving
unsorted array boundary by one element to the right
...

How Selection Sort Works?
Consider the following depicted array as an example
...
The first position where 14 is stored presently, we
search the whole list and find that 10 is the lowest value
...
After one iteration 10, which happens
to be the minimum value in the list, appears in the first position
of the sorted list
...


We find that 14 is the second lowest value in the list and it should
appear at the second place
...


After two iterations, two least values are positioned at the
beginning in a sorted manner
...

Following is a pictorial depiction of the entire sorting process −

Now, let us learn some programming aspects of selection sort
...
With worst-case time complexity being Ο(n log n), it
is one of the most respected algorithms
...

How Merge Sort Works?
To understand merge sort, we take an unsorted array as the
following −

We know that merge sort first divides the whole array iteratively
into equal halves unless the atomic values are achieved
...


This does not change the sequence of appearance of items in the
original
...


We further divide these arrays and we achieve atomic value
which can no more be divided
...
Please note the color codes given to these lists
...
We see that 14 and 33
are in sorted positions
...
We change the
order of 19 and 35 whereas 42 and 44 are placed sequentially
...


After the final merging, the list should look like this −

Now we should learn some programming aspects of merge
sorting
...
By definition, if it is only one element in the
list, it is sorted
...

Step 1 − if it is only one element in the list it is already sorted,
return
...


Step 3 − merge the smaller lists into new list in sorted order
...
As
our algorithms point out two main functions − divide & merge
...

procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0]
...
a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a

end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure



---