정렬 알고리즘 이란?

컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다.

Q. 정렬된 리스트에서 데이터를 찾기 편할까? 정렬되지 않은 리스트에서 데이터를 찾는게 편할까?🤔

A. 말모! 당연히 정렬된 리스트! 👀

1. 버블정렬

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬
단점 : 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

두개의 인접한 수를 비교하고 만약 순서에 맞지 않는다면 교환 하는 방식으로 작동함
N개의 원소에 대해서 버블 정렬은 한번 수행할 때마다 N번째의 원소가 제자리를 찾게 된다.
즉 N개의 요소를 정렬해주기 위해서는 N-1번이 실행되고 최악인 경우 최대한의 횟수를 실행해줘야하므로 경제적이진 않다.

2. 선택정렬

배열안의 자료 중 가장 작은 수 (혹은 가장 큰 수)를 찾아 첫번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬
특징: 선택정렬은 교환횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

주의! step5에서 이미 배열 정렬이 완료되었지만 컴퓨터는 바보이기 때문에 큰 그림을 볼 수 없어서 step6까지 넘어가서 5와6의 크기의 비교를 마친후에야 알고리즘이 종료 된다.

선택정렬은 버블정렬과는 다르게 몇번의 교환을 해주었는지 횟수를 셀필요가없지만 훨씬 더 많은 비교가 필요하므로 비용이 많이 들게된다. 원래의 배열의 순서와 상관없이 선택정렬로 정렬되는 배열은 n-1번의 교환이 필요하다. 그리고 한번의 교환이 일어나기 위해서는 정렬되지 않은 모든 수와 비교가 이루어져야하므로 n2(n의2제곱)번의 비교가 이루어진다. 최악의 경우는 수행하는 횟수만큼 비교과 교환을 해주어야하는 상황이다.

3. 삽입정렬

정렬되지 않은 부분의 자료가 정렬된부분의 자리로 삽입되는 형태의 정렬방법
자료를 여러번 비교하거나 교환할필요가없는 정렬이다.

삽입정렬은 배열을 정렬된 부분과 정렬되지 않은 부분 두개의 부분으로 나누면서 동작하게된다.
삽입정렬은 특정 실행 당계에서, 어떤 원소가 정렬된 배열 내에 자리를 찾았다고 해서 그것이 최종적인 제자리라는 보장은 없다. 다음 단계가 진행되면서 위치가 바뀔 수 있기 때문인데 이때문에 삽입정렬은 자료의 양이 적을 때 높은 성능을 보이게 되며 대부분 이미 정렬이 되어있는 경우에만 효율적이다. 삽입 정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야하는 경우가 발생하면 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮다.