Could someone please help me and tell me why quick sort algorithm will not sort the final element? When I input: 6 89 2 78 12 19 99 43 7 63 I get an ALMOST sorted: 2 6 7 12 78 19 43 99 63 89
I have tried to figure this out my self, but when I work my way thought the code at some point I get lost doing a desk check.
#include <iostream>
using namespace std;
// function prototypes
void quickSort(int arrayList[], int left, int right);
int choosePivot(int arrayList[], int listSize);
int partition(int array[], int left, int right);
void printArray(int theArray[], int Size);
// void swap(int value1, int value2);
int main()
{
int myList[] = {6, 89, 2, 78, 12, 19, 99, 43, 7, 63};
printArray(myList, 10);
quickSort(myList, 0, 9);
printArray(myList, 10);
//int myList2[] = { 7, 4, 9, 10, -9 };
//printArray(myList2, 5);
//quickSort(myList2, 0, 5);
//printArray(myList2, 5);
cin;
getchar;
getchar;
return 0;
}
void quickSort(int arrayList[], int left, int right)
{
//if (left < right)
if(right > left)
{
int p = partition(arrayList, left, right);
printArray(arrayList, 10);
quickSort(arrayList, left, p-1);
quickSort(arrayList, p + 1, right);
}
}
// left (index value) - left most part of the array we are working on
// right (index value) - right most part of the array we are working on
int partition(int array[], int left, int right)
{
//int pivot = array[left]; // I will have to write a function to find the
// optimum pivot point, this is the naive solution
int pivot = array[(left+right)/2];
int i = left;
int j = right;
int temp;
while (i < j)
{
//cout << "in the loop" ;
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i < j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
return i;
}
void printArray(int theArray[], int Size)
{
for (int i = 0; i < Size; i++)
{
cout << theArray[i] << " ";
}
cout << endl ;
}
Aucun commentaire:
Enregistrer un commentaire