열혈 자료구조 - 10.1 단순한 정렬 알고리즘

단순한 정렬 알고리즘

- 구현은 쉽지만 성능은 복잡한 정렬 알고리즘에 비해 떨어짐

- 복잡한 정렬 알고리즘이라 해서 엄청나게 복잡한 것이 아닌 상대적으로 복잡한 것

- 너무 간단해서 다른 기능을 구현할 때 가져와서 사용할 수 있는 장점이 있음

 

버블 정렬

- 인접한 두 요소를 비교하면서 오름차순/내림차순에 따라 값을 뒤로 보냄

- 오름차순 : 큰 값을 뒤로 보냄

- 내림차순 : 작은 값을 뒤로 보냄

- 마지막까지 비교했다면 맨 뒤를 제외하고 다시 반복하는 방식으로 정렬될때까지 반복

void BubbleSort(int arr[], int n)
{
	int i, j;
	int temp;

	for(i=0; i<n-1; i++)
	{
		for(j=0; j<(n-i)-1; j++)	// 반복할때마다 비교하는 인덱스가 줄어 i를 빼줌
		{
			if(arr[j] > arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

- 버블정렬의 시간복잡도 : 4개를 기준으로 3번, 2번, 1번 진행이 됨

 

선택 정렬

- 정렬할 결과를 담을 공간을 따로 마련해놓고 정렬 대상에서 처음부터 끝까지 조회해서 가장 작은(큰) 값을 정렬 결과 공간에 옮기는 정렬법

- 위 방법은 메모리 공간을 따로 요구한다는 단점이 있어 아래와 같이 개선

- 처음부터 끝까지 조회해서 가장 작은 값을 가장 앞으로 이동(교환)

- 가장 앞은 이미 만족했으니 그 뒤부터 가장 끝까지 조회하는 방식으로 반복

void SelSort(int arr[], int n)
{
	int i, j;
	int maxIdx;
	int temp;

	for(i=0; i<n-1; i++)
	{
		maxIdx = i;    // 옮길 위치의 인덱스

		for(j=i+1; j<n; j++)   // 최소값 탐색
		{
			if(arr[j] < arr[maxIdx])
				maxIdx = j;		// 인덱스에 저장
		}

		/* 저장한 인덱스와 교환 */
		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}

- 선택 정렬의 시간복잡도 : 4개를 기준으로 3번, 2번, 1번 진행이 됨

    -> 최악의 경우 최상의 경우 이동의 연산은 동일하게 수행되고 바깥쪽 for문에 있기에 비교 연산보다 적기때문에 비교 연산보다 중요도가 떨어짐

 

삽입 정렬

- 정렬이 된 영역과 정렬이 안된 영역을 나눔

- 순차적으로 정렬이 안된 영역에서 정렬이 된 영역으로 넘겨주고 넘겨줄때 이미 정렬이 되어있는 영역과 비교하여 저장

- 정렬이 안된 영역에서 정렬이 된 영역으로 넘길 때 정렬 위치에 데이터를 옮기면 데이터는 한칸씩 뒤로 옮겨야 함

- 옮길 위치를 찾고 해당 위치부터 뒤로 한칸씩 옮기는 연산이 필요한데 구분을 지어 구현하기보다 하나로 묶는게 편의성을 높일 수 있음

- 정렬된 영역의 뒤부터 하나씩 비교하면서 아니라면 뒤로 한칸 옮기고 맞다면 그 위치에 삽입하는 방식으로 구현

void InserSort(int arr[], int n)
{
	int i, j;
	int insData;

	for(i=1; i<n; i++)	// 첫 데이터는 정렬이 완료됐다고 판단하기 때문에 1부터 시작
	{
		insData = arr[i];   // 정렬 대상을 따로저장

		for(j=i-1; j>=0 ; j--)
		{
			if(arr[j] > insData) 
				arr[j+1] = arr[j];    // 비교 대상 한 칸 뒤로 밀기
			else
				break;   
		}

		arr[j+1] = insData;  // 찾은 위치에 정렬 대상 삽입
	}
}

- 삽입 정렬의 시간복잡도 : 버블과 삽입과 마찬가지