5장 정렬

*버블정렬은 한 번 수행할 때 마다 가장 큰 수가 가장 오른쪽으로 차곡차곡 쌓인다.(오름차순으로 정렬시)

*버블정렬의 일반화식은 n(n-1)/2 이므로, O(n^2) 이다.

void BubbleSort (int DataSet[] , int Length){
	int i = 0;
	int j = 0;
	int temp = 0;

	for ( i = 0 ; i < length -1 ; i ++ ) {
		for ( j = 0 ; j < length - (i+1) ; j ++ ) {
			if(DataSet[j] > DataSet[j+1]) {
				temp = DataSet[j+1];
				DataSet[j+1] = DataSet[j];
				DataSet[j] = temp;
			}
		}
	}
}

*삽입정렬과 버블정렬의 성능은 동일하다. 다만 삽입정렬의 경우 정렬된 데이터에 대해서는 비교를 수행하지 않는다.

void InsertionSort(int DataSet[] , int Length){
	int i = 0;
	int j = 0;
	int value = 0 ;
	for (i = 1 ; i < length ; i ++ ) {
		if( DataSet[i-1] <= DataSet[i])
			continue;
		value = DataSet[i];
		for( j = 0 ; j < i ; j ++ ) {
			if ( DataSet[j] > value) {
				memmove ( &DataSet[j+1], &DataSet[j] , sizeof(DataSet[0]) * (i-j));
				DataSet[j] = value;
				break;
			}
		}
	}
}

*퀵정렬은 분할정복(divide and conquer)방식이다.

#define SWAP(x,y,temp) ( (temp)=(x) , (x),(y) , (y) , (temp))

/*
피벗을 기준으로 2개의 부분 리스트로 분할한다.
피벗보다 작은 값은 왼쪽으로, 피벗보다 큰 값은 오른족 리스트로 옮긴다. 
 */

int partition (int list[] , int left , int right) {
	int pivot;
	int temp;
	int low; //왼쪽에서 올라가는 index
	int high; //오른쪽에 내려오는 index 
	low=left; //
	high = right +1;
	pivot = list[left]; //피벗은 임의로 첫번째 값으로 선택한다.

	/* low high가 교차될 때 까지 반복한다. */
	do{

		/* low가 기준인 피벗보다 클 때 까지 반복한다.*/
		do{
			low++;
		} while(low <= right && list[low] < pivot );

		/* high가 기준인 피벗보다 작을 때 까지 반복한다. */
		do {
			high --;
		} while ( high >= left && list[high] > pivot);

		/* low와 high가 교차하지 않았으면 교환한다. */
		if(low < high)
			SWAP(list[low] , list[high] , temp);
	} while ( low < high );

	/* low와 high가 교차했으면 left(pivot)와 high를 교환한다.*/
	SWAP(list[left] , swap[high] , temp);

	return high; //피벗의 위치를 반환한다. 
}

void QuickSort(int list[] , int left, int right){
	if(left < right){
		int pivotIndex = partition(list , left , right); //divide (리스트를 비균등분할한다.)
		QuickSort(list , left , q-1);
		QuickSort(list , q +1 , right );

	}
}

*반복된 재귀호출은 스택을 메모리에 계속 쌓게 되어 부하의 원인이 된다. 퀵 정렬의 경우 코드가 간결해지고 가독성이 좋기 때문에 재귀를 쓰는게 단점만은 아니지만, 재귀에 대한 부담이 있다면 '꼬리재귀'를 쓰는것도 방법일 수 있다.