[자료구조] L10. Sorting and Searching Algorithms

• toc {:toc}

Sorting

• 정렬 : 선택, 버블, 삽입, 이진, 퀵, 합병

Selection Sort

• 각 pass 마다, 가장 작은 값을 찾고 맨 앞으로 전송한다.

• Linear Search로 순회하면서 가장 작은 값을 찾고 앞으로 보낸다.

• 시간 복잡도 = (n-1) + (n-2) + … + 2 + 1 = O(N^2)

template <class ItemType>
void SelectionSort (ItemType values[ ], int numValues ){
	int endIndex = numValues - 1 ;
	for (int current = 0 ; current < endIndex; current++)
		Swap (values[current], 
			values[MinIndex(values, current, endIndex)]);
}
 
template <class ItemType>
int MinIndex(ItemType values[ ], int start, int end){
	int indexOfMin = start ;
	for(int index = start + 1 ; index <= end ; index++)
		if (values[ index] < values [indexOfMin])
			indexOfMin = index ;
	return indexOfMin;     // 최소값을 갖는 인덱스를 반환
}

Bubble Sort

• 각 pass 마다, 끝에서부터 앞으로 순차적으로 비교하면서 전송한다.
• 시간 복잡도 : (n-1) + (n-2) + … + 2 + 1 = O(N^2) (항상 그런 것은 아니다.)

template<class ItemType>
void BubbleSort(ItemType values[], int numValues){
	int current = 0;
	while (current < numValues - 1){
		BubbleUp(values, current, numValues-1);
		current++;
	}
}
 
template<class ItemType>
void BubbleUp(ItemType values[], int startIndex, int endIndex){
	for (int index = endIndex; index > startIndex; index--)
		if (values[index] < values[index-1])
			Swap(values[index], values[index-1]);
}

Insertion Sort

• 각 pass 마다, 키값을 하나 선택하고 키값이 올바른 위치로 이동하도록 만든다.
• 시간 복잡도 : O(N^2)

template <class ItemType>
void InsertionSort (ItemType values[ ], int numValues )
{
	for (int count = 0 ; count < numValues; count++)
		InsertItem (values , 0 , count);
}
 
template <class ItemType>
void InsertItem (ItemType values[ ], int start, int end){
	bool finished = false;
	int current = end;
	bool moreToSearch = (current != start);
	while (moreToSearch && !finished){
		if (values[current] < values[current - 1]){
			Swap(values[current], values[current - 1);
			current--;
			moreToSearch = ( current != start );
		}
		else
			finished = true ;
	}
}

Heap Sort

• 힙 정렬
  • 정렬되지 않은 트리를 힙 속성이 만족하도록 정렬한다.
  • 루트를 빼고 힙 속성을 만족하도록 정렬하는 과정을 반복한다.
• 시간 복잡도 : (N/2) x O(logN) + (N-1) x O(logN) = O(NlogN)

template <class ItemType>
void HeapSort (ItemType values[ ], int numValues ){
	int index ;
	for (index = numValues/2 - 1; index >= 0; index--)
		ReheapDown ( values , index , numValues - 1 ) ;
 
	// Sort the array.
	for (index = numValues - 1; index >= 1; index--){
		Swap (values [0] , values[index]);
		ReheapDown (values , 0 , index - 1);
	}
}

Quick Sort

• 기준을 설정하고 기준과 비교해 작은 것, 큰 것을 분류한다.
• 왼쪽에서, 오른쪽에서 기준을 설정하고 분류하는 작업을 계속한다.
• 시간 복잡도
  • 기준을 계속해서 중간 값을 갖는 경우 : O(NlogN)
  • 기준이 한쪽 끝으로 몰릴 경우, 최악 : O(N^2)

template <class ItemType>
void QuickSort (ItemType values[ ], int first, int last )
ascending order
{
	if (first < last){
		int splitPoint ;
		Split (values, first, last, splitPoint);
		QuickSort(values, first, splitPoint - 1);
		QuickSort(values, splitPoint + 1, last);
	}
}

Merge Sort

• 합병 정렬 : 계속 분할한 후 합칠 때 비교하여 정렬한다.
• 시간 복잡도 : O(NlogN)

template <class ItemType>
void MergeSort (ItemType values[ ], int first, int last )
{
	if (first < last){
		int middle = ( first + last ) / 2;
		MergeSort(values, first, middle);
		MergeSort(values, middle + 1, last);
		Merge(values, first, middle, middle + 1, last);
	}
}

Testing

• 정렬이 잘 작동하는지를 확인하기 위해서는 다음의 배열을 생성해 테스트해본다.
  • 역순의 배열
  • 거의 정렬된 배열
  • 동일 원소를 가진 배열