Sorting

Merge Sort:

Merge sort is a comparison type of divide and conquer algorithm. It breaks the problem down into smaller individual pieces and compares them to the adjacent list to sort.

Big O notation:

Worst Case: O(n) Average Case: O(nlogn) Best Case: O(nlogn)

Code:

The code is broken down into four different functions

  • ¬† ¬† ¬† ¬† def copy_array: copies the array into a temp.
  • def top_down_merge_sort is the merge sort function which utilizes the rest to complete the algorithm.
  • def top_down_split¬† begins splitting the array into smaller pieces recursively then calls the top down merge to reassemble.
  • def top_down_merge: reassembles the pieces into a sorted array.

 

def top_down_merge_sort(array, temp_array, n):
    top_down_split(temp_array, 0, n, array)

def top_down_split(temp_array, begin_array, end_array, array):
    if(end_array - begin_array < 2):
        return True

    middle = int ((end_array + begin_array)/2)
    top_down_split(array, begin_array, middle, temp_array)
    top_down_split(array, middle, end_array, temp_array)
    top_down_merge(temp_array, begin_array, middle, end_array, array)

def top_down_merge(array, begin, middle, end, temp_array):
    b = begin
    m = middle

    for index in range(begin,end):
        if b < middle and (m >= end or (array[begin] <= array[middle])):
            temp_array[index] = array[b]
            b = b + 1
        else:
            temp_array[index] = array[m]
            m = m + 1

def copy_array(array, temp_array):
    temp_array = array[:]

array = ['h', 'e', 'l','l', 'o']
temp_array = 0
temp_array = array[:]
top_down_merge_sort(array, temp_array, len(array))
print(array)

Quicksort

The Quick Sort was developed in the early 1960s, by Tony Hoarde, since it became one of the most common sorts. The algorithm performs an in-place comparison sort it utilizes very little extra memory on sorting the string. It has a worst case of O(n^2) and a best case of O(nlogn). 

Code: step  example

41      67      34      0       69      24      78      58

swapping: 41 with 41

41      67      34      0       69      24      78      58

41      67      34      0       69      24      78      58

swapping: 67 with 34

41      34      67      0       69      24      78      58

swapping: 67 with 0

41      34      0       67      69      24      78      58

41      34      0       67      69      24      78      58

swapping: 67 with 24

41      34      0       24      69      67      78      58

41      34      0       24      69      67      78      58

swapping: 69 with 58

41      34      0       24      58      67      78      69

the pivot point is: 58

41      34      0       24      58      67      78      69

41      34      0       24      58      67      78      69

swapping: 41 with 0

0       34      41      24      58      67      78      69

swapping: 34 with 24

0       24      41      34      58      67      78      69

the pivot point is: 24

0       24      41      34      58      67      78      69

swapping: 41 with 34

0       24      34      41      58      67      78      69

the pivot point is: 34

swapping: 67 with 67

0       24      34      41      58      67      78      69

0       24      34      41      58      67      78      69

swapping: 78 with 69

0       24      34      41      58      67      69      78

the pivot point is: 69

0       24      34      41      58      67      69      78

Code:

#include¬†‚Äúiostream‚ÄĚ
#include¬†‚Äúrandom‚ÄĚ
using namespace std;
void quickSort(int list[8],int high,int low);
int partition(int list[8],int high,int low);
int main()
{
 int list[8];
 for(int index =0; index < 8; index++)
 {
    list[index] = rand()%100;
¬†¬†¬†¬†cout¬†<<¬†list[index]¬†<<¬†‚Äė\t‚Äô;
 }
 cout << endl;
 quickSort(list,7,0);
 for(int index =0; index < 8; index++)
 {
¬†¬†¬†¬†cout¬†<<¬†list[index]¬†<<¬†‚Äė\t‚Äô;
 }
 return 0;
}
void quickSort(int list[8],int high,int low)
{
 int temp;
 if(low < high)
 {
    temp = partition(list, high,low);
    cout << “the pivot point is: “ << list[temp] << endl;
¬†¬†¬†¬†quickSort(list,temp‚Äď1,low);
    quickSort(list, high, temp+1);
 }
};
int partition(int list[8],int high,int low)
{
 int pivot = list[high];
¬†int¬†lo¬†=¬†low‚Äď1;
 int temp;
 for(int index = low; index < high; index++)
 {
    if(list[index] < pivot)
    {
     lo+=1;
¬†¬†¬†¬†¬†cout¬†<<¬†‚Äúswapping: ‚Äú¬†<<¬†list[lo]¬†<<¬†‚ÄĚ with ‚Äú¬†<<¬†list[index]¬†<<¬†endl;
     temp = list[lo];
     list[lo] = list[index];
     list[index] = temp;
    }
    for(int index =0; index < 8; index++)
    {
¬†¬†¬†¬†¬†cout¬†<<¬†list[index]¬†<<¬†‚Äė\t‚Äô;
    } cout << endl;
 }
 if(list[high] < list[lo+1])
 {
¬†¬†¬†¬†¬†cout¬†<<¬†‚Äúswapping: ‚Äú¬†<<¬†list[lo+1]¬†<<¬†‚ÄĚ with ‚Äú¬†<<¬†list[high]¬†<<¬†endl;
    temp = list[lo+1];
    list[lo+1] = list[high];
    list[high] = temp;
 }
 for(int index =0; index < 8; index++)
 {
¬†¬†¬†¬†cout¬†<<¬†list[index]¬†<<¬†‚Äė\t‚Äô;
 } cout << endl;
 return lo+1;
};