[알고리즘] 정렬: 연속된 데이터를 기준에 따라 정렬

정렬 알고리즘 개요

졍렬(Sorting)이란 데이터를 특정 기준에 따라 순서대로 나열하는 것이며, 정렬 알고리즘으로 정렬 시 이진탐색이 가능해진다.

(이진탐색의 전처리과정)

 

많이 사용하는 정렬 알고리즘

선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

 

선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸기를 반복

매번 가장 작은 것을 '선택'

 

삽입 정렬

선택 정렬에 비해 구현 난이도 높으나 데이터가 거의 정렬되어 있을 때 효율적

특정한 데이터를 적정한 위치에 '삽입'

 

퀵 정렬

정렬 라이브러리의 근간, 기준 데이터 설정 후 비교해가며 위치 변경, 가장 많이 사용

피벗 사용, 데이터의 개수가 많을수록 선택,삽입 정렬에 비해 압도적으로 빠른 속도

이미 데이터가 정렬되어 있을 경우 느림

 

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능

계수 정렬 이용시 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에 조건부 사용

비교 기반의 알고리즘이 아니며, 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키며 정렬