[Algorithms] 정렬 알고리즘(Sorting algorithms)

정렬 알고리즘(Sorting algorithms)

정렬 알고리즘 종류

- 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬, 셸 정렬, 퀵 정렬, 병합 정렬, 힙 정렬, 도수 정렬 등

Time complexity of sorting algorithms: https://afteracademy.com/blog/comparison-of-sorting-algorithms/

 

정렬(Sorting)

정렬(sorting): 이름, 학번, 학점 등의 key를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업(swap)

정렬 알고리즘의 핵심: 교환, 선택, 삽입

교환(swap)	두 변수에 들어 있는 값을 서로 맞바꾸는 연산
선택(select)	주어진 조건에 따라 선택적으로 명령을 실행하는 것
삽입(insert)	원하는 위치에 원하는 값을 추가하는 것

오름차순과 내림차순(Ascending and Descending)

https://www.mathswithmum.com/ascending-descending-order/

오름차순(ascending order) 정렬: 값이 작은 데이터를 앞쪽에 늘어놓는 것 = 점점 커지는 것 → ex: 1, 2, 3, 4, 5

내림차순(descending order) 정렬: 값이 큰 데이터를 앞쪽에 늘어놓는 것 = 점점 작아지는 것→ ex: 5, 4, 3, 2, 1

 

정렬 알고리즘의 안정성(Stability of sorting algorithms)

https://testbook.com/question-answer/what-is-mean-by-stable-sorting-algorithm--5ec69b5bf60d5d3a7c491cdb

안정적인 정렬(stable sorting): 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것 → i와 j의 값의 순서가 m, n이 동일

안정적이지 않은 정렬(unstable sorting): 정렬한 후에 값이 같은 원소의 순서가 원래대로 유지된다는 보장을 할 수 없음 → i가 j보다 앞에 있었으나 정렬 후에 i가 n의 자리로, j는 m의 자리로 swap 되면서 기존의 같은 값의 원소 순서가 동일하지 않음

- 참고할 만한 영상: https://www.youtube.com/watch?v=ClG4xjwQ0BM

 

내부 정렬 vs 외부 정렬(Internal sorting vs External sorting)

내부 정렬: 정렬할 모든 데이터를 하나의 배열에서 작업할 수 있는 경우에 사용하는 알고리즘

외부 정렬: 정렬해야 할 데이터가 많아서 여러 배열로 작업해야 하는 경우에 사용하는 알고리즘

ex: 만약 학생이 30명일 때, 한 반에 모두 앉힐 수 있겠지만 학생 수가 300명이라면 여러 반으로 나눠야하므로 더 많은 반이 필요

이 때 한 반만 있어도 되는 경우, 즉, 하나의 배열에서 작업할 수 있으면 내부 정렬을 사용함

하지만 학생 수가 많아 여러 반이 필요한 경우, 즉, 2개 이상의 배열에서 작업해야 하는 경우 외부 정렬을 사용함