뇌를 자극하는 알고리즘(Data Structures In C) - 5. 정렬 : Quick Sort

구현소스

QuickSort.h

#ifndef QUICKSORT_H
#define QUICKSORT_H

#include <stdio.h>

void Quick_Sort(int Data[], int left, int right, int size);
int Partition(int Data[], int left,int right);
void Swap(int *a, int *b);

void Print_Array(int Data[], int size);

#endif

------------------------------------------------------------------
QuickSort.cpp

#include "QuickSort.h"


void Print_Array(int Data[], int size){
	int i;
	static int count = 0;
	printf("%d. Current Array : ", ++count);
	for(i=0;i<size;i++)
		for(i=0;i<size;i++)
			printf("%d, ", Data[i]);
		printf("\n");

}
void Quick_Sort(int Data[], int left, int right, int size){
	Print_Array(Data,size);
	if(left<right)
	{		
		int q=Partition(Data,left,right);
		Quick_Sort(Data,left,q-1,size);		
		Quick_Sort(Data,q+1,right,size);
		
	}
}
void Swap(int *a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

// Data[] = {2, 3, 1, 4, 5};
// Quick_Sort(Data, left = 0, right = 4, size = 5)
//..- if문 0<4 이므로 
//..- q = Partition(Data, left=0, right=4)
//..- Partition(Data, left=0, right=4)
//.....- low = left = 0
//.....- high = right+1 = 5
//.....- pivot = Data[left=0] = 2
//.....- do while~ low<high
//.......- do while~ Data[low] < pivot
//..........- low =1 일때 Data[1]=3 > pivot 이므로 loop 탈출
//.......- low = 1
//.......- do while~ Data[high] > pivot
//..........- high = 2일때 Data[2]=1 < pivot 이므로 loop 탈출
//.......- if(low= 1 < high =2) 이므로 Swap(&Data[low=1], &Data[high=2]);

//    ****   Current Data[] = {2, 1, 3, 4, 5} ****

//.....- low=1 < high=2 이므로 while문 반복
//.......- do while~ Data[low] < pivot
//..........- low = 2일때 Data[2] = 3 > pivot 이므로 loop 탈출
//.......- do while~ Data[high] > pivot
//..........- high=1 일때 Data[1] = 1 < pivot 이므로 loop 탈출
//.......- if(low=2 < high =1) 성립하지 않으므로 통과
//.....- low=2 < high=1 이 성립하지 않으므로 while문 통과
//.....- Swap(&Data[left=0], &Data[high=1]);
//.....- return high=1;

//    ****   Current Data[] = {1, 2, 3, 4, 5} ****

// q = 1
// Quick_Sort(Data,left,q-1,size);		
// Quick_Sort(Data,q+1,right,size);

// Quick_Sort(Data,left=0,right=q-1(1-1=0),size);	
//..- if(left=0 < right=0) 이므로 함수 호출 종료

// Quick_Sort(Data,left = q+1 = 2, right=4, size)
//..- if(left=2 < right=4) 이므로
//..- q = Partition(Data, left=2, right=4)
//..- Partition(Data, left=2, right=4)
//.....- low = left = 2
//.....- high = right+1 = 5
//.....- pivot = Data[left=2] = 3
//.....- do while~ low=2 <high=5
//.......- do while~ Data[low] < pivot
//..........- low =3 일때 Data[3]=4 > pivot=3 이므로 loop 탈출
//.......- low = 3
//.......- do while~ Data[high] > pivot
//..........- high = 2일때 Data[2]=3 == pivot=3 이므로 loop 탈출
//.......- high = 2
//.......- if(low= 3 < high =2) 성립하지 않으므로 통과
//.....- low=3 < high=2 이 성립하지 않으므로 while문 통과
//.....- Swap(&Data[left=2], &Data[high=2]);
//.....- return high=2;

//    ****   Current Data[] = {1, 2, 3, 4, 5} ****

// q=2
// Quick_Sort(Data,left=2,q-1=1,size); // if문 성립 안되므로 함수 호출 종료		
// Quick_Sort(Data,q+1=3,right=4,size);
//..- if(left=3 < right=4) 이므로
//..- q = Partition(Data, left=3, right=4)
//..- Partition(Data, left=3, right=4)
//.....- low = left = 3
//.....- high = right+1 = 5
//.....- pivot = Data[left=3] = 4
//.....- do while~ low=3 <high=5
//.......- do while~ Data[low] < pivot
//..........- low =4 일때 Data[4]=5 > pivot=4 이므로 loop 탈출
//.......- low = 4
//.......- do while~ Data[high] > pivot
//..........- high = 3일때 Data[3]=4 == pivot=4 이므로 loop 탈출
//.......- high = 3
//.......- if(low= 4 < high =3) 성립하지 않으므로 통과
//.....- low=4 < high=3 이 성립하지 않으므로 while문 통과
//.....- Swap(&Data[left=3], &Data[high=3]);
//.....- return high=3;

//    ****   Current Data[] = {1, 2, 3, 4, 5} ****
// q=3
// Quick_Sort(Data,left=3,q-1=2,size); // if문 성립 안되므로 함수 호출 종료		
// Quick_Sort(Data,q+1=4,right=4,size);// if문 성립 안되므로 함수 호출 종료	

// 정렬 완료
//    ****   Current Data[] = {1, 2, 3, 4, 5} ****

int Partition(int Data[], int left, int right){
	int pivot; // pivot을 기준으로 Data배열의 pivot 왼쪽에는 pivot보다 작은 데이터들을
			  // 오른쪽에는 pivot보다 큰 데이터들을 구성시킨다.
	int low, high;

	low = left; 
	high = right+1;
	pivot = Data[left]; // pivot은 정렬할 리스트의 가장 왼쪽 데이터를 선택한다. 
						// - 주로 사용되는 방법은 리스트 내의 몇 개의 데이터중에서 중간 값을 피벗으로 선택
	// low는 왼쪽 데이터에 들어갈 데이터들을 탐색하는데 쓰이고
	// high는 오른쪽 데이터에 들어갈 데이터들을 탐색하는데 쓰인다.

	do
	{
		do
		{
			low++;
		}
//		while(Data[low] > pivot); //내림차순
		while(Data[low] < pivot); //오름차순

		do
		{
			high--;
		}
//		while(Data[high] < pivot); //내림차순
		while(Data[high] > pivot); //오름차순

		if(low<high)
			Swap(&Data[low], &Data[high]);

	} while(low<high);

	Swap(&Data[left], &Data[high]);

	return high;

}

------------------------------------------------------------------
main.cpp

#include "QuickSort.h"

int main(){

	int Data[] = {2, 3, 1, 4, 5};

	Quick_Sort(Data,0, ( sizeof(Data)/sizeof(int) ) - 1, sizeof(Data)/sizeof(int) );

	return 0;
}

------------------------------------------------------------------

실행결과

오름차순

내림차순