자바 기초 - 새싹과정 5주차 (4)

<알고리즘>

정렬 알고리즘이란?

-리스트 안에 저장된 요소들을 특정한 순서대로 배치하는 알고리즘

-집합데이터를 사용 (콜렉션)

-compable 함수 이용하여 정렬 -> sort명령을 통해 정렬 가능

 

<선택정렬>

-선택데이터가 다른 값들보다 작으면 앞으로 정렬

-가장 안정적

-시간적으로 오래 걸림. 

 

<삽입정렬>

-더 작은 값의 자리를 바꿔주는 정렬

-바뀐 자리에서 이전 값들과도 비교해야 함.

-복잡하지만 속도가 빠름

 

<버블정렬>

-바로 옆 두 데이터 (서로 인접한 요소들)를 비교해서 정렬 (옆에 있는거끼리 크냐 작냐 비교)

-추가적인 메모리 소비가 작음.

-앞에서 부터 차례대로 비교해 나가기 때문에 안정적임.

-but, 상대적으로 다른 정렬 알고리즘에 비해 비교과정이 많아 데이터가 많아질수록 많은 시간 소비. 

(시간복잡도: O(N2))

 

*정렬 방법

1. 맨 앞부터 현재 요소와 바로 그 다음 요소를 비교한다.
2. 만약, 현재 요소가 다음요소보다 크면 자리를 교체한다.
3. 다음 두번째 자리의 요소와 그 다음 요소를 비교 (즉, 비교 후 한 칸씩 이동해서 비교) 

출처:&nbsp;st-lab.tistory.com

 

*전체적인 흐름 방식

https://en.wikipedia.org/wiki/Bubble_sort

 

<병합정렬>

-병합이란? : 여러 개로 쪼개진 요소들을 다시 합치는 것

-즉, 병합정렬은 데이터를 작은 집합으로 정렬해서 다시 조립하는 방식 

-구조상 최대한 작게 리스트를 쪼개어 앞의 부분리스트부터 차례대로 정렬하기 때문에 안정적.

-또한 최악의 경우에도 시간 복잡도가 O(NlogN)으로 유지됨.

-메모리에 부하를 줌. (데이터를 작은 집합으로 묶어서 한번 더 정렬하기 때문에 추가적으로 배열 공간을 사용.)

 

 

*정렬방법

1. 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (분할)
2. 부분리스트가 더 이상 나누어지지 않을 때까지 1번 과정을 반복한다. 
3. 더 이상 나누어지지 않는(서로 인접한) 부분리스트들부터 정렬하면서 합친다.(정복)

출처: st-lab.tistory.com

 

*전체적인 흐름

https://en.wikipedia.org/wiki/Merge_sort

 

<힙 정렬>

-완전 이진트리여야만 가능

-실생활에서는 잘 사용하지 않음.

 

<퀵 정렬>

-임의의 기준 데이터 값(피벗)을 정하고 해당 피벗으로 집합을 기준으로 부분 집합을 나눔.

-피벗 값이 값들을 비교하면서, 피벗보다 큰 값을 오른쪽, 작은 값은 왼쪽에 저장. (오른쪽으로 갈 수록 큰 값의 경우)

-더 이상 쪼갤 집합이 없을 때까지 각각의 집합을 위와 같은 방식으로 진행해서 정렬.

 

*정렬 방법

1. 임의의 피벗 값을 선택함.
2. 피벗을 기준으로 양쪽에서 피벗 값을 찾는다. (피벗 값을 기준으로 왼쪽은 피벗보다 큰 값/ 오른쪽은 피벗보다 작은 값)
3. 양 방향에서 찾은 두 요소를 교환한다.
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을때까지 2번으로 돌아가 위 과정을 반복한다.
5. 엇갈린 기점(만나는 부분)을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐때 까지 과정을 반복한다.
6. 인접한 부분리스트끼리 합친다.

[맨 마지막 값을 피벗으로 설정할 때의 과정]

출처:&nbsp;https://st-lab.tistory.com/250

 

 

*전체적인 흐름

출처:&nbsp;https://visualgo.net/en

 

<기수 정렬>

-비교연산을 통해 정렬 순서를 정하지 않음.

-자릿수 비교를 통해 정렬하는 방식

-낮은 자리 수부터 비교하여 정렬 (일의 자리-> 십의 자리-> 백의 자리, ... 순으로)

-정렬 속도가 빠르지만 메모리가 더 필요함. 

 

*정렬 방법 

 ex) [5 , 73, 48, 24, 15, 89]를 정렬

1. 가장 큰 자릿수 값 구함. (-> 89 = 10의 자릿수)
2. 가장 작은 1의 자리 숫자만 비교하여 정렬 -> [73, 24, 5, 15, 48, 89]
3. 10의 자리 숫자만 비교하여 정렬 -> [5, 15, 24, 48, 73, 89]

 

*전체적인 흐름

출처 : https://hyo-ue4study.tistory.com

 

<정렬 시 고려사항>

-시간 복잡도 고려 (빅오 표기법)

-메모리 사용량

-안정성 (stability) 데이터 순서가 바뀌지 않느냐 여부

 * 모든 정렬 알고리즘은 같은 키를 가진 데이터의 순서를 안바꾼다라고 잘못 생각함.

 

[빅오표기법 - BigO]

*정렬 알고리즘 비교

출처:&nbsp;https://blog.naver.com/PostList.naver?blogId=aa991102

 

<정렬 알고리즘 선택할 때 고려사항>

-정렬할 데이터 양

-데이터와 메모리

-이미 정렬된 정도

-추가메모리의 양

-상대 위치 보존여부(안정성) 등

 -> 1,2,4번은 enterprise에서 크게 고려되지 않음.

 

 

• 출처 : https://hyo-ue4study.tistory.com/m/68

[알고리즘]정렬 알고리즘의 선택과 종류 7가지

 

• https://st-lab.tistory.com/category/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

'알고리즘' 카테고리의 글 목록