[자료구조] 자료구조 정리 및 정렬 알고리즘

자료구조 종류

• 배열(리스트)
  • 링크드 리스트
• 스택
• 큐
  • 우선순위 큐
• 그래프
  • 인접 행렬 그래프 → 2차원 배열
    지도나 행렬이 주어졌을 때 ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  • 인접 리스트 그래프 → 링크드 리스트
    일부 간선의 정보만 주어졌을 때 ex) [(a, b, d1), (a, c, d2), (b, d, d3)]
    
    
  • 트리
    • 이진트리
    • 힙
      트리의 변형으로 최대, 최소 값을 찾기 위해 고안됨 → 우선순위 큐
• 해쉬

 

+ 해쉬와 링크드 리스트

링크드는 리스트 안에 각자 다음 노드를 표시해 놓는 것

해쉬는 키와 밸류를 이어 놓은 테이블을 따로 생성하는 것

---

정렬 종류

• 선택 정렬, selection sort
  • 전체를 순회하면서 가장 작은 값을 저장해서 순회가 끝났을 때 저장
  • 시간복잡도
    무조건 O(n**2)
• 버블 정렬, bubble sort
  • 앞 뒤를 비교하면서 가장 큰 값을 끝까지 가져가 고정하는 방식
  • 시간복잡도
    선택 정렬과 같다

선택 정렬과 버블 정렬의 경우 방식의 차이일 뿐 시간은 같기 때문에 취향차이이다. 그리고 구리기 때문에 이론만 알고 가자.

---

• 삽입 정렬, insertion sort
  • 리스트에 숫자를 삽입하면서 자신의 위치가 되면 삽입
  • 시간복잡도
    이미 정렬되어 있는 리스트에 삽입하면 O(n), 최악의 경우 O(n**2)
• 셸 정렬, shell sort
  • 삽입정렬을 보완한 알고리즘 삽입정렬의 경우 하나씩 넘어가면서 비교하여 삽입했다면, 셸 정렬은 정의된 크기만큼 빅스텝으로 넘어 갈 수 있다.
  • 시간 복잡도
    삽입정렬과 같지만, 평균적으로 O(n**1.5)

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog

---

• 합병 정렬, merge sort
  • 재귀함수를 활용한 정렬이다. 두 리스트에서 첫 번째 값을 비교하면서 작은 것을 담는 알고리즘
  • 시간복잡도
  • 무조건 O(n log n)
  • 공간 복잡도
  • 배열 두개를 사용한다 → 2N

• 퀵 정렬, quick sort
  • 구현 방법
    1. 아무 피벗이나 설정한다, 대부분 중앙값
    2. 왼쪽 끝 low, 오른쪽 끝 high로 포인터를 정의하고 low는 피벗보다 큰 데이터를 찾으면 멈춘다. high는 피벗보다 작은 데이터를 찾으면 멈춘다. *피벗은 무시하고 넘어가니까 아무 값이나 되어도 상관없다.
    3. 두 데이터를 교환한다.
    4. high ≤ low면 피벗과 high를 교환한다.
    5. 재귀
  • 시간복잡도 O(n log n)
    → 깊이 log n * 배열당 시간 n
    한개씩만 짤리면 깊이가 n이 되고 → 최악의 경우 깊이 n * 배열당 시간 n
    
    
  • 문제점
    정렬된 리스트일 경우 오히려 오래 걸림
    → 불균형 분할이기 때문
    → 그나마 이 단점을 해결하기 위해 중앙 값을 설정하면 좀 덜함
    
    
  • 공간복잡도는 O(log n)
    recursion 방식이기 때문에 recursion memory를 사용

그래도 제일 빠르다

 

 

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

[정렬 알고리즘] 퀵 정렬 - 피벗을 선택하는 두 가지 방법

---

• 힙 소트, heap sort
  • 힙의 최대, 최소 기능을 활용한 알고리즘
    • 힙의 경우 최대, 최소값 탐색시간 O(1) 삽입, 삭제시 O(log n)
  • 시간 복잡도 O(n log n) 힙 정렬이 가장 유용한 경우는 전체 정렬이 아니라 → 가장 큰 값 몇개만 필요할 때!
  • 공간 복잡도 In place 알고리즘이기 때문에 메모리 이득 O(1) 

---

 

+ 이외에도 기수정렬, 계수정렬 등등이 있다.

 

+ 공간 복잡도 계산

    한 배열에서만 진행을 하면 O(n)이다

 

+ 정렬 알고리즘의 가장 빠른 속도는 O(n log n)이다

    키 비교에 의한 정렬 알고리즘은 결국 이진트리 방식이기 때문!

    → 깊이 log n * 배열당 시간 n

    log n 보다 작은 깊이가 나올 수가 없다.

정렬이 O(n log n)보다 빠를 수 없을까❓

 

+ 안정 정렬이란?

    중복된 값을 입력 순서와 동일하게 정렬 → 안정적

    안정 정렬 : 삽입 정렬, 병합 정렬, 버블 정렬

    불안정 정렬 : 퀵정렬, 선택정렬

---

참고자료

[Data Structure] 자료구조란? 기본 자료 구조 - 배열(Array), 링크드리스트(LinkedList), 스택(Stack), 큐(Queue

기본 정렬 알고리즘(Sorting Algoritm) 요약 정리 (선택, 삽입, 버블, 합병, 퀵) v1.1