본문으로 바로가기
정렬 알고리즘 개요

Name 

Best

Worst (Big-O)

Stable 

Memory 

선택정렬

False

1

버블정렬

n

True

1

삽입정렬

n

True

1

합병정렬

nlogn

nlogn

True

n

힙 정렬

 

nlogn


1

퀵 정렬

 nlogn

nlogn

 False

1



1. 선택정렬(Selection Sort)

① 개요 
      • 한번 순회를 하면서 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.
      • 최소 선택 정렬(Min-Selection Sort) : 오름차순으로 정렬
      • 최대 선택 정렬(Max-Selection Sort) : 내림차순으로 정렬
② 기본 로직
      1.  정렬 되지 않은 인덱스의 맨 앞부터, 그 이후의 배열값 중 가장 작은 값을 찾아간다.
      2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
      3. 위 과정을 반복한다.

③ 복잡도
      1. 시간복잡도 O => n-1, n-2, .... , 1개씩 비교를 반복하므로 대략 n(n-1) / 2번 수행된다.
      2. 공간복잡도 O

④ 코드 





2. 버블정렬(Bubble Sort)

① 개요 
      • 바로 가까이에 있는 두 숫자끼리 비교를 해서 더 작은 숫자를 앞으로 보내주는 것을 반복
      • 비교할 때마다 큰 값이 뒤로 이동하여, 1바퀴 돌 때 가장 큰 값이 맨 뒤에 저장된다.
      • (전체 배열의 크기 - 현재까지 순환한 바퀴 수) 만큼만 반복
      • 컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 안 좋은 알고리즘
② 기본 로직
      1. 두 번째 인덱스부터 시작한다. 현재 인덱스 값과 바로 이전 인덱스 값을 비교한다.
      2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
      3. 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.
      4. (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

③ 복잡도
      1. 시간복잡도 O
      2. 공간복잡도 O

④ 코드 



3. 삽입정렬(Insertion Sort)

① 개요 
      • 현재 Index 위치에서 현재 Index보다 작은쪽을 비교하여 자신이 들어갈 위치를 찾아 삽입하는 알고리즘
      • 기본적으로 정렬 되어 있다는 상황에서 가장 빠른 알고리즘 ▶O)
② 기본 로직
      1. 두 번째 Index부터 시작한다. 현재 Index 값은 별도의 변수(currentValue)에 저장하고, 비교 Index(Position)를 현재 Index로 잡는다.
      2. 별도로 저장해 둔 삽입을 위한 변수(currentValue)와 비교 Index-1 의 배열 값을 비교한다.
      3. 삽입 변수의 값이 더 작으면 현재 Index-1의 값을 저장해주고, 비교 Index(Position)를 -1하여 비교를 반복한다.
      4. 만약 삽입 변수가 더 크면 while문을 빠져나와 비교 Index(Position)에 삽입 변수를 저장한다.

③ 복잡도
      1. 시간복잡도 O) , 참고로 Best일 때  : O) : while문 조건에서 O(1)이기 때문에
      2. 공간복잡도 O

④ 코드 










댓글을 달아 주세요