정렬 알고리즘 part1

정렬 알고리즘 part 1에선, 빅-오 성능 n^2인 알고리즘 들을 살펴보겠다.
쉽게 말해 알고리즘 성능이 좋지 않은 정렬 방법들을 살펴본다.

정렬 알고리즘을 항상 외우고 있을 필요는 없다고 생각한다.
허나, 필요할 때 어떤 알고리즘 이였지? 라는 질문에 대한 답을 이 글에서 찾길 바라는 마음에 정리하였다.

소스 구현 및 테스트는 따로 하였으나 본 글에는 소스를 적진 않으며, 알고리즘 설명을 위해 ppt 이미지를 많이 첨부하게 되었다.

버블 정렬

버블 정렬은 인접한 요소들을 비교하는 방법으로 데이터를 정렬하며 각 라운드에서 최대값을 먼저 정렬하는 방법이다.

알고리즘

4개의 데이터를 정렬하기 위한 1 라운드 과정이다. 인접한 요소들을 비교해 큰 값을 뒤로 이동 시키며, 1라운드가 끝나면 가장 큰 데이터가 맨 뒤로 정렬된다.

버블 정렬의 2라운드 과정이다. 1라운드를 통해 가장 큰 값이 맨 뒤로 정렬되었으니, 나머지 3개의 데이터만 정렬하면 된다.

마지막 3라운드 과정이다. 1,2 라운드를 통해 4개의 데이터 중 가장 큰 값 두개가 맨뒤에 정렬이 되었다. 따라서 남은 2개만 비교하여 정렬의 위치를 찾으면 된다.

성능평가

n개의 데이터를 버블 정렬 시킬 경우, n-1 라운드가 필요하며, 각 라운드가 끝나면 비교할 대상이 한 개씩 줄어든다. 이를 알면 아래의 성능평가를 이해할 수 있다.

선택 정렬

선택 정렬은 정렬 순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되는 알고리즘이다. 예를 들면, 가장 작은 데이터를 선택해 첫 번째 자리로 옮기고, 두 번째로 작은 데이터를 선택해 두 번째 자리로 옮긴다.

알고리즘

아래 그림은 선택 정렬 시, 각 라운드에 따른 정렬 순서를 보여준다.

1 라운드에서는 가장 작은 값 1을 첫 번째 자리로 옮기고,

2 라운드에서는 두 번째로 작은 값 2를 두 번째 자리로 옮기며,

3 라운드에서는 세 번째로 작은 값 3을 세번째 자리로 옮긴다.

위의 버블 정렬과는 달리 각 라운드가 끝난 결과만을 보여준다. (일일히 그리기 힘들다 ㅠ)

성능평가

데이터 n개를 선택정렬 하기 위해 n-1 라운드가 필요하며, 각 라운드마다 최소 값을 찾는 루프가 존재한다. 이에 따른 성능평가는 아래와 같다.

삽입정렬

삽입 정렬은 정렬되지 않은 부분과 정렬된 부분으로 나눈다. 그리고 정렬되지 않은 부분의 각 요소를 삽입하는 과정에서 정렬이 진행된다.

그림으로 보는게 빠르다.

알고리즘

아래 그림에서 첫 번째 라운드의 정렬을 통해 정렬 된 부분과 정렬되지 않은 부분으로 나눈다. 그리고 정렬되지 않은 데이터 4, 1을 맞는 위치에 삽입함으로써 정렬을 완성한다.

성능평가

삽입 정렬도 위 정렬 알고리즘과 마찬가지로, n개의 데이터 정렬을 위해 n-1라운드가 필요하며 각 라운드마다 삽입 위치를 찾기위한 루프가 존재한다.