버블정렬(bubble sort) - 알고리즘

버블정렬(bubble sort)

인접한 두 데이터 A[ i ]와 A[ i+1 ] 비교

A[ i + 1 ] < A [ i ]

→ 두 데이터 교환

→ 가장 큰 데이터가 배열의 끝에 위치

데이터 양이 많을 때 비효율적

 

시간복잡도(time complexity)

최악+ 최선 + 평균 → O(n^2)

 

 

선택정렬알고리즘 (Selection sort algorithm)

각 반복에서 제일 큰 값(또는 제일 작은 값) 을 '선택' 해서, 그 값을 차례로 교환하여 정렬을 이뤄나가는 방식

 

선택정렬의 종류

→ 최소 선택정렬(min selection sort)

     최소 데이터부터 차례러 정렬 (오름차순 정렬)

→ 최대 선택정렬(max selection sort)

     최대 데이터부터 차례로 정렬 (내림차순 정렬)

 

시간복잡도(time complexity)

→ O(n^2)

 

최대 선택 정렬 (max selection sort)

알고리즘 A

→ 각 칸의 데이터를 찾기 위해, 앞의 모든 데이터와 비교 교환

 

알고리즘 B

→ 각 칸의 데이터를 찾기 위해, 앞에서 가장 큰 데이터 보관 교환

삽입 정렬 (insertion sort algorithm)

삽입할 데이터를 (왼쪽의) 정렬되어 있는 부분의 올바른 위치에 삽입 하는과정 반복

 

시간복잡도(time complexity)

최악+ 최선 + 평균 → O(n^2)

 

퀵 정렬 (quick sort)

 

time complexity (시간복잡도)

   균형 → O(nlog n)

   불균형 → O(n^2)

왼쪽은 피봇보다 작은값 오른쪽은 피봇보다 큰 값

 

※ 분할과 정복 (Divide and Conquer) 방법에 의한 정렬이다.

 

개선된 quick sort 알고리즘

L

→ 왼쪽에서 오른쪽으로 진행

→ 피벗보다 큰 데이터를 찾으면 STOP

R

→ 오른쪽에서 왼쪽으로 진행

→ 피벗보다 작은 데이터를 찾으면 STOP

 

→ L과 R을 교환

→ R과 피벗을 교환

 

합병 정렬(merge sort) 방식

time complexity (시간복잡도)

최악 + 최적 + 평균 = O(nlog n)

 

단점 

→ 데이터를 배열(Array)에 저장하면 여분 배열

→ 데이터가 많은 경우 이동 횟수가 많아서 시간 낭비 발생

장점

→ 안정적인 정렬 방법 O(nlog n)

→ 데이터를 연결 리스트(Linked List) 에 저장하면 여분 장소 불요 (in-place sorting 가능)

    → 크기가 큰 데이터 정렬시, 연결 리스트 사용하면, 매우 효율적

 

기수 정렬 알고리즘 radix sort algorithm  

좌선 정렬 (left first sort)

→ 최대 유효 숫자 정렬

→ 큰 단위에서 작은 단위로 키를 이동

(백 자리 → 십 자리 → 일 자리)

 

우선 정렬(right first sort)

→ 최소 유효 숫자 정렬

→ 작은 단위에서 큰 단위로 키를 이동

(일 자리 → 십 자리 → 백 자리)

 

※ 비교가 아닌 분배에 의한 정렬이다.

 

힙 알고리즘 heap sort algorithm 

partially ordered tree

임의의 노드에 있는 데이터는 아들 데이터보다 크다(or 작다)

 

최대 히프 (max heap)

→ 부모 노드의 키값이 자신 노드의 키값보다 큰 complete binary tree

최소 히프 (min heap)

→ 부모 노드의 키값이 자식 노드의 키값보다 작은 complete binary tree

 

최대 힙 삭제 연산

→ 항상 루트를 삭제하고 맨 마지막 원소를 루트에 올림

→ 루트를 그 자식 중 큰 것과 비교해 자리 바꿈 한다. 이를 단말 레벨까지 반복한다. (top-down 방식)

 

시간복잡도(time complexity)

최악+ 최선 + 평균 → O(n log n)

7급 공무원 시험 2013 자료구조론 4번문제