자료구조 정렬(Sorting) 기초 개념 정리

버블정렬(Bubble Sort)

버블정렬이란 인접한 두개의 데이터를 비교해서 정렬을 진행하는 방법이다.

버블정렬의 성능은 좋은편은 아니다. (정렬알고리즘에서 성능은 비교의 횟수와 이동의 횟수를 근거)

ex) 배열에 숫자들을 오름차순으로 정렬할때 첫번째 수를 시작으로 끝의 숫자까지 인접한 수와 비교하고 이동한다.

선택정렬(Selection Sort)

선택정렬이란 제자리정렬 알고리즘중 하나이며, 오름차순으로 정렬한다면 가장 작은 최솟값을 맨앞에 놓고 그 이후의 값들을 하나씩 비교한 후 올바른 값을 선택하여 채워넣는 정렬방법입니다.

버블정렬과 비슷한 성능을 가지고 있다.

삽입정렬(Insertion Sort) 

삽입정렬은 정렬대상을 정렬된 부분과 안된부분으로 두 부분으로 나눈 후 정렬안된부분의 데이터를 정렬된부분의 특정위치에 삽입하는 정렬방법입니다.(=정렬이 완료된 영역 다음에 위치한 데이터가 다음 정렬대상)

병합정렬(Merge Sort)

병합정렬은 분할정복 알고리즘 디자인기법에 근거하여 만들어졌으며, 데이터를 통째로 정렬하는 것보다 나눠서 정렬하는 것이 더 쉽다는 전제하에 데이터의 영역을 나눠서 정렬하는 방법입니다.

병합정렬은 데이터가 1개가 남을때까지 분할한다. (정렬 X , 분할만) 그 후 다시 병합을 하면서 정렬을 한다.

분할정복(3단계): 분할(문제를분할) -> 정복(분할돤문제를해결) -> 결합(해결한결과를결합)

기수정렬(Radix Sort)

기수정렬은 기존에 정렬들과는 다르게 정렬순성상에 우선순위를 판단하기 위한 비교연산을 하지않으며, 기수를 이용해서 정렬을 진행한다. 

기수정렬은 길이가 같은 데이터들을 대상으로만 정렬이 가능하다. (길이가 다르더라도 가능은 하지만 상당히 제한적)

일반적으로 기수정렬은 LSD 방식을 기준으로 한다.

기수: 주어진 데이터를 구성하는 기본 요소 ex) 2진수의 기수는 0과 1, 10진수의 기수는 0~9

LSD(Least Significant Digit): 덜 중요한 자릿수부터 정렬을 시작

MSD(Most Significant Digit): 가장 중요한 자릿수(큰자릿수)부터 정렬을 시작