C++

Forum

 
Question on quicksort

wakaka3910 (3)
I would like to ask about ascending quick sort. The program goes in infinite loops when I try to stop the while loop.
As an example, we have a input sort 37 2 6 4 89 8 10 12 68 45.

Starting from the rightmost element of the array, compare each element with 37 until an element less than 37 is found. Then swap 37 and that element. Then the array will become 21 2 6 4 89 8 10 37 68 45.

After that starting from the left of the array, but beginning with the element after 12, compare each element with 37 until an element greater than 37 is found. Then swap 37 and that element. The array will become 12 2 6 4 37 8 10 89 68 45.

These processes continue until 37 is at the right place so that the array is 12 2 6 4 10 8 37 89 68 45. Then loop the function again for {12, 2, 6, 4, 10, 8} and {89, 68, 45}. Thanks a lot.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include<iostream>
#include<iomanip>
using namespace std;

int a[10];
int* aptr = a;

void quickSort(int arr[], int start, int end)
{
	int o = start;
	int p = end;
	int midValue = arr[o];
	int midPosition = o;
	int oo = start;
	int pp = end;

	while (oo < pp)
	{
		for (int i = p ; arr[i] > o ; i--)
		{
			if (arr[i] < midValue)
			{
				swap(arr[i], arr[o]);
				midPosition = i;
				pp = i;
				break;
			}
		}
		for (int i = o ; arr[i] < p ; i++)
		{
			if (arr[i] > midValue)
			{
				swap(arr[o], arr[midPosition]);
				midPosition = i;
				oo = i;
				break;
			}
		}
	}
	if (midPosition != 0 && midPosition != 9)
	{
		quickSort(arr, start, midPosition - 1);
		quickSort(arr, midPosition + 1, end);
	}
	else if (midPosition == 0)
	{
		quickSort(arr, midPosition + 1, end);
	}
	else
	{
		quickSort(arr, 0, midPosition - start);
	}
}



int main()
{
	int values, origin;
	cout << "Initial array values are:" << endl;
	for (int i = 0; i < 10; i++)
	{
		cin >> values;
		a[i] = values;
	}
	quickSort(a, 0, 9);
	cout << "\nThe sorted array values are:" << endl;
	cout << setw(6) << a[0] << setw(6) << a[1] << setw(6) << a[2] << setw(6) << a[3] << setw(6) << a[4];
	cout << setw(6) << a[5] << setw(6) << a[6] << setw(6) << a[7] << setw(6) << a[8] << setw(6) << a[9] << endl;
	return 0;
}
Repeater (3046)
Your quicksort function will never end. It has no return and it will always call quicksort again, forever and ever.
wakaka3910 (3)
Sorry do you mean the whole quicksort function or the while loop need to return something?
Repeater (3046)
Functions end when they reach the last } , or when they return. Your quicksort function doesn't do either of those. How is your quicksort function meant to know when to stop?
wakaka3910 (3)
Ah thx finally did it
Topic archived. No new replies allowed.