퀵소팅 알고리즘

퀵소팅 알고리즘 연습.. 

N2 의 연산량을 갖는 퀵소팅 ..   

우선순위 큐// 

N log(N) 

아래 두 내용을 등호를 바꾸게 되면 , 내림 / 오름 차순의 알고리즘으로 변경 

주의해야할 점은 복사 하면서 오타 나느거 i,j 그리고 부등호 .. 조심

void QSort(int first, int last)
{
	int pivot;
	int i;
	int j;
	int temp, temp2; 

	if (first < last)
	{
		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i] > input[pivot] && i < last)
			{
				i++;
			}

			


			while (input[j] < input[pivot])
			{
				j--;
			}


			while (input[i] == input[pivot] && i < last)
			{
				if (time[i] > time[pivot])
					i++;
				else
					break;
			}

			while (input[j] == input[pivot])
			{

				if (time[j] < time[pivot])
					j--;
				else
					break;		
			
			}

			

			


			if (i < j)
			{
				temp = input[i];
				input[i] = input[j];
				input[j] = temp;

				temp2 = time[i];
				time[i] = time[j];
				time[j] = temp2;

			}
		}

		temp = input[pivot];
		input[pivot] = input[j];
		input[j] = temp;

		temp2 = time[pivot];
		time[pivot] = time[j];
		time[j] = temp2;

		QSort(first, j - 1);
		QSort(j + 1, last);
	}
}




while (i <= end && data[i] <= data[pivot]){
        i++;
}
while (j > start && data[j] >= data[pivot]){
	j--;
}






#include 
#include 

using namespace std;



int data[10] = { 4, 1, 2, 3, 9, 7, 8, 6, 10, 5 };

void quick_sort(int *data, int start, int end){
	if (start >= end){
		// 원소가 1개인 경우
		return;
	}

	int pivot = start;
	int i = pivot + 1; // 왼쪽 출발 지점 
	int j = end; // 오른쪽 출발 지점
	int temp;

	while (i <= j){
		// 포인터가 엇갈릴때까지 반복
		while (i <= end && data[i] <= data[pivot]){
			i++;
		}
		while (j > start && data[j] >= data[pivot]){
			j--;
		}

		if (i > j){
			// 엇갈림
			temp = data[j];
			data[j] = data[pivot];
			data[pivot] = temp;
		}
		else{
			// i번째와 j번째를 스왑
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	// 분할 계산
	quick_sort(data, start, j - 1);
	quick_sort(data, j + 1, end);
}

int main(void){
	quick_sort(data, 0, 9);

	// 결과 확인
	for (int i = 0; i<10; i++){
		printf("%d ", data[i]);
	}

	cout << endl;


	return 0;
}