Search the entire list and "select" the element with the smallest (largest) value and swap it with the element at the top of the list.
Repeat until size-1 passes have been made through the list
Original: 8 6 34 2 51 32 21 Pass 1: 2 6 34 8 51 32 21 Pass 2: 2 6 34 8 51 32 21 Pass 3: 2 6 8 34 51 32 21 Pass 4: 2 6 8 21 51 32 34 Pass 5: 2 6 8 21 32 51 34 Pass 6: 2 6 8 21 32 34 51
TOP => subscript of the first element
LAST => subscript of the last element
SSF => subscript of the smallest element
PTR => subscript to go through the array
DO WHILE (TOP < LAST)
PTR = TOP
SSF = TOP
DO WHILE (PTR < LAST)
IF (AR[PTR] < AR[SSF])
SSF = PTR
ENDIF
PTR = PTR + 1
ENDDO
SWAP AR[TOP] and AR[SSF]
TOP = TOP + 1
ENDDO
Each loop will execute at most N (or size) times, therefore this sort is O(N2). If the array is already sorted, the algorithm will still be O(N2).
Examine the elements at positions x and x+1. Put them in ascending (descending) order. No examine the elements at positions x+1 and x+2. Put them in ascending (descending) order. Repeat until the end of the list is reached.
Repeat the process but limit the size of the list by 1 for each subsequent pass.
Original: 8 6 34 2 51 32 21
Pass 1: 6 8 34 2 51 32 21
6 8 34 2 51 32 21
6 8 2 34 51 32 21
6 8 2 34 51 32 21
6 8 2 34 32 51 21
6 8 2 34 32 21 51
6 8 2 34 32 21 51
Pass 2: 6 8 2 34 32 21 51
6 2 8 34 32 21 51
6 2 8 34 32 21 51
6 2 8 32 34 21 51
6 2 8 32 21 34 51
6 2 8 32 21 34 51
I, J => subscripts to go through the array
END => subscript of the last element
FLAG => indicates that a swap has occurred (1 = yes, 0 = no)
FLAG = 1
DO WHILE (FLAG = 1 AND END > 0)
I = 0
J = 1
FLAG = 0
DO WHILE (J <= END)
IF (AR[I] > AR[J])
FLAG = 1
SWAP AR[I] and AR[J]
ENDIF
I = I + 1
J = J + 1
ENDDO
END = END - 1
ENDDO
Each loop will execute at most N (or size) times, therefore this sort is O(N2). If the array is already sorted, the algorithm will still be O(N2).
Repeat until x = size-1
Original: 8 6 34 2 51 32 21 Pass 1: 6 8 34 2 51 32 21 Pass 2: 6 8 34 2 51 32 21 Pass 3: 2 6 8 34 51 32 21 Pass 4: 2 6 8 34 51 32 21 Pass 5: 2 6 8 32 34 51 21 Pass 6: 2 6 8 21 32 34 51
LOW => subscript of the first element
HIGH => subscript of the last element
J, K => subscripts
J = LOW + 1
DO WHILE (J <= HIGH)
K = J
DO WHILE (K > LOW AND AR[K] < AR[K-1])
SWAP AR[K] and AR[K-1]
K = K - 1
ENDDO
J = J + 1
ENDDO
Each loop will execute at most N (or size) times, therefore this sort is O(N2). If the array is already sorted, the algorithm will be O(N).
The shell sort examines and sorts every nth element of a list. This process continues with the (n+1)th elements of the list. Once all of the list elements have been examined one time, the value of n is decreased.
The process starts over with the new value of n and continues until n becomes 1.
Because the value of n is diminishing with each pass through the algorithm, the shell sort is known as a diminishing increment sort.
Initial n value: size / 2
Subsequent n values: n / 2
Original: 8 6 34 2 51 32 21
n = 3 2 6 32 8 51 34 21
2 6 32 8 51 34 21
n = 1 2 6 8 21 32 34 51
template<class T>
void shellSort( T ar[], int size)
{
int j;
for( int gap = size / 2; gap > 0; gap /= 2 )
for( int i = gap; i < size; i++ )
{
T temp = ar[i];
for( j = i; j >= gap && temp < ar[j-gap]; j -= gap )
ar[j] = ar[j-gap];
ar[j] = temp;
}
}
The running time for this sort depends on the choice of n.
Using the calculation above, this is an O(N2) algorithm.
The algorithm can be made more effective by using increments 1, 3, 7, ..., 2k-1. This sequence will keep the consecutive elements from having common factors. This will produce an algorithm that is O(N3/2).
The merge sort divides the list of elements in half. The left half of the list is sorted. The right half of the list is sorted. The two sorted lists are then merged into one large list.
Original: 8 6 34 2 51 32 21
8 6 34 2 51 32 21
2 6 8 34 21 32 51
2 6 8 21 32 34 51
template<class T>
void mergeSort( T ar[], int size)
{
T *tempArray = new T[size];
mergeSort( ar, tempArray, 0, size-1 );
}
template<class T>
void mergeSort( T ar[], T temp[], int left, int right )
{
if( left < right )
{
int center = (left + right) / 2;
mergeSort( ar, temp, left, center );
mergeSort( ar, temp, center+1, right );
merge( ar, temp, left, center+1, right;
}
}
template<class T>
void merge( T ar[], T temp[], int lPos, int rPos, int rEnd )
{
int lEnd = rPos - 1,
tempPos = lPos,
numElem = rEnd - lPos + 1;
while( lPos <= lEnd && rPos <= rEnd )
if( ar[lPos] <= ar[rPos] )
temp[tempPos++] = ar[lPos++];
else
temp[tempPos++] = ar[rPos++];
while( lPos <= lEnd )
temp[tempPos++] = ar[lPos++];
while( rPos <= rEnd )
temp[tempPos++] = ar[rPos++];
for( int i = 0; i < numElems; i++, rEnd-- )
ar[rEnd] = temp[rEnd];
}
Since the routine is recursive, a recurrence relation must be determined to calculate the running time of the algorithm.
For a list of size 1, the time to merge sort is constant.
T(1) = 1
Otherwise, the recursive call is dealing with half of the list T(n/2), plus the time to merge, which is linear N.
T(n) = T(n/2) + T(n/2) + n = 2T(n/2) + n
T(n) = 2T(n/2) + n
T(n/2) = 2T(n/2/2) + n/2 = 2T(n/4) + n/2
2T(n/2) = 4T(n/4) + n
2T(n/2) + n = 4T(n/4) + 2n
T(n) = 2T(n/2) + n = 4T(n/4) + 2n
In general: T(n) = 2kT(n/2k) + kn
Solve this for k: n/2k = 1
n = 2k
log n = k
T(n) = 2log n T(n/2log n) + n log n
= n T(n/n) + n log n
= n T(1) + n log n
= n * 1 + n log n
= n + n log n
O(n + n log n) = O(n log n)
Quick sort uses a divide and conquer strategy to sort a list. The list is divided into three segments: left, middle, and right.
The middle segment consists of only one element, which is known as the pivot.
The left segment consists of all of the elements that are smaller than the pivot.
The right segment consists of all of the elements that are larger than the pivot.
Pseudocode
if size of list is greater than 1 select the pivot partition the remaining elements into the segments left and right quicksort(left) quicksort(right) endif
| 13 | 81 | 92 | 43 | 65 | 31 | 57 | 26 | 75 | 0 |
Lets pick 65 as the pivot. Then partitioning the list around the pivot results in:
| 13 | 43 | 31 | 57 | 26 | 0 | 65 | 81 | 92 | 75 |
Quicksorting the left and right segments results in:
| 0 | 13 | 26 | 31 | 43 | 57 | 65 | 75 | 81 | 92 |
This is okay if the elements in the list are random. If the list is sorted or in reverse order, this is a poor choice because all of the elements will end up in either the left or right segment.
This option is usually pretty safe, except for the fact that the random number generation is expensive.
Find the first, middle, and last element in the array. Use the median of the three as the pivot.
The partition operation is implemented by searching the list from both the beginning and end. The search from the beginning will be looking for elements that are greater than the pivot, while the search from the end is looking for elements that are less than or equal to the pivot.
Once each search finds an element, if the two pointers have not met, then the two values are swapped. The process will continue until the two searches meet or surpass each other.
Once the two searches have met or surpassed, the smaller of the elements is swapped with the pivot.
1. Swap the pivot element with last element
8 1 4 9 6 3 5 2 7 0
8 1 4 9 0 3 5 2 7 6
2. Set i to the first element and j to the next to last element
8 1 4 9 0 3 5 2 7 6
i j
3. Move i to the right until it refers to an element that is larger than
the pivot value
8 1 4 9 0 3 5 2 7 6
i j
4. Move j to the left until it refers to an element that is smaller than
the pivot value
8 1 4 9 0 3 5 2 7 6
i j
5. If i is to the left of j, swap the elements at positions i and j
8 1 4 9 0 3 5 2 7 6
i j
2 1 4 9 0 3 5 2 7 6
i j
6. Continue the process until i and j meet or i surpasses j
2 1 4 9 0 3 5 2 7 6
i j
2 1 4 5 0 3 9 2 7 6
i j
2 1 4 5 0 3 9 2 7 6
j i
7. Swap the pivot element and the element at position i
2 1 4 5 0 3 6 2 7 9
template class T
int partition( T list[], int left, int right)
{
calculate the center using left and right subscripts
calculate the pivot
while left < right
while list[right] > pivot
decrement right
endwhile
while list[left] <= pivot AND left < right
increment left
endwhile
if left < right
swap list[left] and list[right]
endif
endwhile
swap pivot and list[left]
return left
}
Now the pseudocode for quicksort can be refined to:
quicksort(list, first, last) if first < last partition (list, first, last, pivotPosition) quicksort(list, first, pivotPosition - 1) quicksort(list, pivotPosition + 1, last) endif
Since the routine is recursive, a recurrence relation must be determined to calculate the running time of the algorithm.
The running time is equal to the running time of the two recursive calls plus the linear time for the partitioning:
T(n) = T(i) + T(n - i - 1) + cn
T(n) = 1 for n <= 1
where i is the size of the left segment.
Worst case: pivot is the smallest element all of the time. Then i = 0:
T(n) = T(n-1) + cn for n > 1
T(n-1) = T(n-2) + c(n-1)
T(n-2) = T(n-3) + c(n-2)
T(n-3) = T(n-4) + c(n-3)
...
T(2) = T(1) + c(2)
Summing both sides results in:
T(n) + T(n-1) + T(n-2) + T(n-3) + ... + T(2) = T(n-1) + cn + T(n-2) + c(n-1) + T(n-3) + c(n-2) + T(n-4) + c(n-3) + ... + T(1) + c(2)
Eliminating like terms results in:
T(n) = cn + c(n-1) + c(n-2) + ... + 2c + T(1)
= c( n + (n-1) + (n-2) + ... + 2 ) + T(1)
= c ∑i + T(1) (the basic series)
= n(1 - n) / 2
= n(1 - n)
= n - n2
= O(N2)
Best case: pivot is in the middle
To make the math easier, assume that the subarrays are exactly half the size of the original. This results in the recurrence relation:
T(n) = 2T(n/2) + cn
which was solved earlier for O(n log n).