Sorting Algorithm

Quicksort

/ Developer: Austin / Leave a comment

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).

It is first going to select the pivot as the last number in the list

pivot = 58

Then it assigns lo = -1

For each number from 0 to pivot’s position

If a number in that list is less than the pivot number

Then lo is incremented

and it swaps the index number with the number at the lo position

If the number at the end of the list is less than the number at the lo+1 Position

then swap them

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

 

#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;
};