학습 일자 : 2023.04.28

선형 정렬

일렬로 된 자료를 정렬하는 방법.

1개의 요소를 재위치시키기 위해 전체를 확인하는 과정을 반복한다. (n개의 요소를 재위치시키기 위해 n개를 확인함)

시간복잡도 : O(N^2)

선택정렬

데이터를 전부 확인하며 가장 조건에 맞는 데이터를 하나씩 선택하며 정렬

(오름차순 정렬 시) 현재 데이터보다 가장 작은 값의 위치를 선택, 해당 값의 위치와 현재 위치를 바꿈

public void SelectionSort(IList<int> list)
{
	for (int i = 0; i < list.Count; i++)
	{
		int minIndex = i; //현재 데이터 
		for (int j = i + 1; j < list.Count; j++)
		{
			if (list[j] < list[minIndex])
				minIndex = j; //현재 데이터보가 가장 작은 값의 인덱스를 찾음
		}
		Swap(list, i, minIndex); //찾은 제일 작은 값과 현재 위치를 바꿈
	}
}

삽입정렬

데이터를 하나씩 꺼내어 정렬 된 자료 중 적합한 위치를 찾아 삽입하여 정렬

(오름차순 정렬 시) 자신보다 작은 데이터가 나올 때까지 한칸씩 이동하면서 자리를 찾아감

public void InsertionSort(IList<int> list)
{
	for (int i = 1; i < list.Count; i++)
	{
		int key = list[i]; //데이터를 꺼냄
		int j = i - 1; //현재 위치 이전 데이터만 확인함 
									 //(이전 위치는 이미 정렬되어 있기 때문에 그 안에서 내 위치만 찾으면 돼)
		for (; j >= 0 && key < list[j]; j--) 
		{ 
			list[j + 1] = list[j]; 
		}
		list[j + 1] = key;
	}
}

버블 정렬

서로 인접한 데이터를 비교하며 정렬. (ex.키순으로 줄 세우기)

버블 정렬 최적화 : 순회하면서 한번도 값을 바꾸지 않았다면 정렬을 종료함.

public void BubbleSort(IList<int> list)
{
	for (int i = 0; i < list.Count; i++)
	{
		for (int j = 1; j < list.Count; j++)
		{
			if (list[j - 1] > list[j]) //비교는 본인 바로 뒤 인덱스랑만 비교함
				Swap(list, j - 1, j);
		}
	}
}

분할정복 정렬

큰 문제를 잘게 쪼개서 해결하는 방식으로 재귀적 개념을 내포하고 있음.