[C#] 정렬 알고리즘 (선택 정렬, 버블 정렬)

인벤토리가 있는 게임을 하다보면 정렬 기능이 거의 존재한다. 하지만 이게 어떤

방식으로 동작하여 차례대로 정렬되는지 딱히 생각하지 않고 사용한다.

그래서 정렬 알고리즘이 왜 사용되며 어떤 방식으로 적용되는지 알아보고자 한다.

 

 

정렬 알고리즘이란?

정렬 알고리즘이란 데이터를 특정한 순서대로 배열하는 프로세스를 말한다.

대표적인 정렬 알고리즘으로는 버블, 삽입, 선택, 병합, 퀵 정렬이 있다.

이를 사용하는 이유는 데이터를 더 빠르게 탐색하고, 이해하기 쉽게 만들며, 

데이터 처리의 효율성을 높이기 위해서다.

 

C#의 대표적인 정렬 메서드는 다음과 같다.

 

OdrerBy : 값을 오름차순으로 정렬

 

OrderByDesending : 값을 내림차순으로 정렬

 

ThenBy: 2차 정렬을 오름차순으로 수행

 

ThenByDesending: 2차 정렬을 내림차순으로 수행

 

Reverse: 컬렉션의 요소 순서를 반대로 바꾼다.

 

그럼 정렬 알고리즘을 배우면서 가장 많이 접하게 되는 버블 정렬과 선택 정렬에 대해 

설명하고자 한다.

 

 

버블 정렬

버블 정렬은 인접한 두 원소를 비교 하여 정렬하는 방법이다

 

5, 2, 6 란 데이터를 오름차순 정렬한다고 가정하면 인접한 두 원소인

5와 2를 5 > 2 형태로 비교한다. -> 2, 5, 6

다시 5와 6을 5 > 6 형태로 비교한다 -> 2, 5, 6

 

이렇게 A > B라는 조건식을 이용하여 하나씩 위치를 바꿔나가는 방식을 사용한다.

이러한 방식으로 처음부터 n - 1까지 비교해서 정렬한다.

 

버블 정렬 코드

 

 

선택 정렬

오름차순 정렬을 한다고 가정하면 인덱스 0부터 시작하여 데이터 리스트중에 가장 작은 값을

찾아내어 인덱스를 교환하는 방식이다.

 

5, 2, 3, 1 이라는 데이터 리스트가 있다고 가정하면 인덱스가 0인 5의 위치부터 시작하여 차례대로

데이터를 탐색한다. 그러면 1이라는 최소 값을 발견하게 되고 5와 1의 위치가 바뀌게 된다.

이러한 방식으로 정렬을 n - 1까지 진행한다.

 

선택 정렬 코드

 

 

오늘 선택 정렬과 버블 정렬에 대해 알아봤는데 사실 이 정렬 알고리즘들은

O(N)^2의 시간복잡도를 가지고 있어서 사용을 안하는 것이 좋다.

자료의 개수가 적다면 괜찮지만 자료가 1억개가 있다고 가정하면 1억 ^ 2

개의 자료를 비교해야한다. 어마어마한 수가 될 것이다.

그렇기 때문에 O(N)이나 O(nlogn)을 가진 정렬 알고리즘들을 찾아 사용하는 것이

바람직하다.