사실 알고리즘을 공부하려고 한 건 아니고 자료구조를 보던 중 자연스래 나오길래!
정리를 합니다!

정렬 알고리즘

특정한 기준에 따라 순서대로 나열 하는 것
문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용함.

선택정렬

• 계속하여 가장 작은 값을 찾고 맨 앞에 차곡차곡 쌓는 방법
• 시간 복잡도가 좋지 않음 O(n^2)

삽입정렬

• 이미 정렬돼있으면 가장 빠르다
• 앞 쪽 데이터가 이미 정렬돼있다 가정하고 어디에 들어갈지 찾는거
• 최악의 경우 O(n^2) 최선의 경우 O(n)

퀵 정렬

• C, 자바, 파이썬의 표준 정렬 알고리즘
• 병합 정렬이랑 더불어 자주 사용함
• 기준 데이터를 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 보통 첫 번째 데이터를 피벗으로 설정
• 왼쪽에서부터 피벗보다 큰 값, 오른쪽에서 피벗보다 작은 값을 찾고, 둘다 찾으면 서로 위치를 바꿈 ! 반복!
• 만약 찾은 두 값의 위치가 엇갈리면 작은 데이터랑 피벗이랑 바꿔줌
• 그리고 피벗을 기준으로 나뉜 두 배열을 계속 퀵소트함
• 평균 O(NlogN), 최악의 경우 O(N^2) -> 정렬된 경우!

계수 정렬

• 특정 조건이 부합할 때 사용이 가능하고 매우 빠르게 동작하는 정렬 알고리즘
  - 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
• 데이터 개수 N, 최댓값 K이면 O(N+K)보장
• 최소값이랑 최대값까지 인덱스 리스트를 만들고 데이터 배열을 순회하며 인덱스 리스트에 값을 증가시킴
• 다 순회하면 인덱스 리스트 값을 뽑아내면서 정렬 완료

참고자료

(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘