Quicksort to sort integers

closed account (jEb91hU5)
Is there something wrong in my quicksort code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
  void QuickSort(int A[], int left, int right)
{
	int j, k;
	
	if (left < right)
	{
		j = left;
		k = right + 1;
		do
		{
			do
				j++;
			while (A[j] < A[left] && j <= k);
		
			do
				k--;
			while (A[left] < A[k] && k >= 0);

			if (j < k)
			{
				swapem(A[left], A[k]);
			}
		} while (j <= k);

		QuickSort(A, left, k - 1);
		QuickSort(A, k + 1, right);
	}
}
lastchance (6980)
You will get more answers if you provide complete code - it is irritating to have to write a driver to test this.

You would be better doing the loop tests at the top of the loop rather than at the bottom; some loops do not need to run.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <iostream>
#include <algorithm>
using namespace std;

void QuickSort(int A[], int left, int right)
{
        if (left < right)
        {
                int value = A[left];
                int j = left;
                int k = right;
                while ( j <= k )
                {
                        while (A[j] < value) j++;
                        while (A[k] > value) k--;
                        if (j >= k) break;
                        swap(A[j], A[k]);
                        j++; k--;
                }

                QuickSort(A, left, k );
                QuickSort(A, k + 1, right);
        }
}

int main()
{
    int A[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    int N = sizeof A / sizeof A[0];
    for ( int i = 0; i < N; i++ ) cout << A[i] << ' ';
    cout << '\n';
    QuickSort( A, 0, N - 1 );
    for ( int i = 0; i < N; i++ ) cout << A[i] << ' ';
    cout << '\n';
}



My preferred version (but there are many):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <iostream>
#include <algorithm>
using namespace std;

void QuickSort( int A[], int left, int right )
{
   if ( right <= left ) return;
   int value = A[(left+right)/2];                // many choices

   // Partition such that  A{ left . . k }  <=  value  <=  A{ k+1 . . right }
   int j = left  - 1;
   int k = right + 1;
   while ( true )
   {
      do j++; while ( A[j] < value );
      do k--; while ( A[k] > value );
      if ( j >= k ) break;                       // if pointers cross, then done
      swap( A[j], A[k] );                        // move elements into the other partition
   }

   QuickSort( A, left , k  );
   QuickSort( A, k + 1, right );
}

int main()
{
    int A[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    //int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    //int A[] = { 5, 5, 5, 5, 5 };
    //int A[] = { 5, 4, 3, 2, 1, 1, 2, 3, 4, 5 };
    int N = sizeof A / sizeof A[0];
    for ( int i = 0; i < N; i++ ) cout << A[i] << ' ';
    cout << '\n';
    QuickSort( A, 0, N - 1 );
    for ( int i = 0; i < N; i++ ) cout << A[i] << ' ';
    cout << '\n';
}

Last edited on
closed account (jEb91hU5)
So sorry about that. I'll know for next time. I also realized the mistake I made. Thanks for your help! :)
Topic archived. No new replies allowed.