[JAVA] 정렬 종류와 정의

정렬 종류와 정의

 

정렬의 정의 :

데이터를 정해진 순서로 재배열하는 것(오름차순, 내림차순)

정렬은 비교와 교환의 미학

수 많은 정렬 알고리즘이 존재함.

 

선택 정렬(Selection sort)   

(최소값의 인덱스를 찾아서 정렬되지 않은 부분의 제일 앞으로 보내기 )

(교환회수가 적어서 큰 레코드를 다룰 때 적합)

 

선택 정렬은  제자리 정렬 알고리즘의 하나로

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

 

선택 정렬(selection sort) 알고리즘의 예제
배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

1회전:
첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.
2회전:
두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.
3회전:
세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.
4회전:
네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

 

 

버블 정렬 (Bubble Sort)

(인접요소의 비교/교환을 통해 최대값을 제일 뒤로 보낸다.)(뒷쪽부터 정렬된다는 특징이있고 교환 횟수가 매우 많아 느리다)

 

버블 정렬(bubble sort) 알고리즘의 예제
배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

1회전
첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
2회전
첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
3회전
첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
4회전
첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

 

 

​삽입 정렬 (Insertion Sort)

(정렬되지 않은 원소를 정렬된 리스트에 적합한 위치를 찾아 삽입하는 것)

​(거의 정렬이 되어있는 문제에는 빠르다)

​

​느린 정렬 알고리즘 비교

 

퀵 정렬(Quick Sort)

 

개선된 퀵 정렬(Improved Quick Sort)

 

쉘정렬(Sheel Sort)

 

 

병합 정렬(Mergr Sort)

 

힙 정렬(Heap Sort)