Changing this quicksort always use the last item as a bar

Question

I have Quicksort that always selects the first element of a subsequence as a set:

void qqsort(int array[], int start, int end) { int i = start; // index of left-to-right scan int k = end; // index of right-to-left scan if (end - start >= 1) { // check that there are at least two elements to sort int pivot = array[start]; // set the pivot as the first element in the partition while (k > i) { // while the scan indices from left and right have not met, while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first element greater than the pivot i++; while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first element not greater than the pivot k--; if (k > i) // if the left seekindex is still smaller than the right index, swap the corresponding elements swap(array, i, k); } swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot qqsort(array, start, k - 1); // quicksort the left partition qqsort(array, k + 1, end); // quicksort the right partition } else { // if there is only one element in the partition, do not do any sorting return; } } 

Now, as you can see, this algorithm always takes the first element as a rotation: int pivot = array[start];

I want to change this algorithm so that it always uses the last element instead of the first element of the subsequence, because I want to analyze the physical runtime of both implementations.

I tried changing the line int pivot = array[start]; on int pivot = array[end]; , but then the algorithm deduced an unsorted sequence:

 //Changes: int pivot = array[end]; unsorted: {5 4 3 2 1} *sorted*: {1 2 5 4 3} 

To test another element, I also tried using the central element of the subsequence, but the algorithm still failed:

 //Changes: int pivot = array[(start + end) / 2]; unsorted: {5 3 4 2 1} *sorted*: {3 2 4 1 5} 

---

Can someone please help me understand this algorithm correctly and tell me what changes I need to make in order to successfully implement this implementation, always select the last element of the subsequence as a fulcrum?

Answer 1

Cause of the problem

The problem is that you are using int k = end; . It was nice to use int i = start; when you had the rotation element as the first element in the array, because your checks in the loop will pass by it ( array[i] <= pivot ). However, when you use the last element as a rotation, k stops at the end of the index and switches the axis of rotation to the position in the left half of the section. You already have problems, because your core will most likely be somewhere inside the left section, and not on the border.

Decision

To fix this, you need to set int k = end - 1; when you use the rightmost element as a fulcrum. You will also need to change the lines to replace the code with the border between the left and right sections:

 swap(array, i, end); qqsort(array, start, i - 1); qqsort(array, i + 1, end); 

You should use me for this because I will end up in the leftmost element of the right section (which can then be swapped while in the rightmost element and it will keep order). Finally, you want to change k >= i to k > i at a time that decreases k, or there is a small change in the indexing error [-1]. This was impossible because I was always at least equal to + 1 to this point.

That should do it.

Sidenote:

This is a poorly written operating system that I would not recommend learning. It has some extraneous, unnecessary comparisons along with some other drawbacks that I will not waste time listing. I would recommend using quicksorts in this presentation from Sedgewick and Bentley.

Answer 2

I have not tested it, but check it out anyway:

this is

 // after the indices have crossed, // swap the last element in the left partition with the pivot swap(array, start, k); 

probably should be

 swap(array, end, i); 

or something like that if we choose end as the pivot point.

Edit: This is an interesting partitioning algorithm, but it is not standard.

Well, the core is fixed in the partitioning logic.
The algorithm treats the first element as the Head element and the rest as the body to be split.
After the partition is completed, as a last step, the head (rotation) is replaced by the last element of the left sectioned part to maintain order.

The only way I decided to use another element without changing the algorithm is as follows:

 ... if (end - start >= 1) { // Swap the 1st element (Head) with the pivot swap(array, start, pivot_index); int pivot = array[start]; ... 

Answer 3

The first hint: if the data is random, on average it doesn’t matter which value you choose as the rotation axis. The only way to really improve the "quality" of the joint is to take more (for example, 3) indices and use one with a median value of them.

Second hint: if you change the rotation value, you also need to change the rotation index. This is not explicitly stated, but array[start] is replaced with the "middle" of the sorted subsequence at one point. You must modify this line accordingly. If you take an index that is not on the edge of a subsequence, you need to swap it to the edge first before iterating.

Third hint: the code you provided is over commented. You should be able to understand this implementation.

Answer 4

Put single

 swap(array, start, end) 

before initializing the rod

 int pivot = array[start] 

Answer 5

 #include <time.h> #include <stdlib.h> #include<iostream> #include<fstream> using namespace std; int counter=0; void disp(int *a,int n) { for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; } void swap(int a[],int p,int q) { int temp; temp=a[p]; a[p]=a[q]; a[q]=temp; } int partition(int a[], int p, int start, int end) { swap(a,p,start);// to swap the pivot with the first element of the partition counter+=end-start; // instead of (end-start+1) int i=start+1; for(int j=start+1 ; j<=end ; j++) { if(a[j]<a[start]) { swap(a,j,i); i++; } } swap(a,start,i-1); // not swap(a,p,i-1) because p and start were already swaped..... this was the earlier mistake comitted return i-1; // returning the adress of pivot } void quicksort(int a[],int start,int end) { if(start>=end) return; int p=end; // here we are choosing last element of the sub array as pivot // here p is the index of the array where pivot is chosen randomly int index=partition(a,p,start,end); quicksort(a,start,index-1); quicksort(a,index+1,end); } int main() { ifstream fin("data.txt"); int count=0; int array[100000]; while(fin>>array[count]) { count++; } quicksort(array,0,count-1); /* int a[]={32,56,34,45,23,54,78}; int n=sizeof(a)/sizeof(int); disp(a,n); quicksort(a,0,n-1); disp(a,n);*/ cout<<endl<<counter; return 0; } 

Answer 6

If you start monitoring each element from the 1st element of the array to the last - 1, holding the last element as a support for each recursion, you will receive an answer in the exact <strong> O (NlogN) time.

 #include<stdio.h> void quicksort(int [], int, int); int main() { int n, i = 0, a[20]; scanf("%d", &n); while(i < n) scanf("%d", &a[i++]); quicksort(a, 0, n - 1); i = 0; while(i < n) printf("%d", a[i++]); } void quicksort(int a[], int p, int r) { int i, j, x, temp; if(p < r) { i = p; x = a[r]; for(j = p; j < r; j++) { if(a[j] <= x) { if(a[j] <a[i]) { temp = a[j]; a[j] = a[i]; a[i] = temp; } i++; } else { temp = a[i]; a[i] = a[j]; a[j] = temp; } } if(x != i) { temp = a[r]; a[r] = a[i]; a[i] = temp; } quicksort(a, p, i - 1); quicksort(a, i + 1, r); } }