본문 바로가기

정렬2

[자료구조] 정렬 (sorting) - 퀵, 힙, 병합, 기수 정렬 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 복습 앞서 학습했던 Big-O 표기법을 숙지해가며 공부하자. 스택(LIFO) : 가장 나중에 들어온 데이터가 먼저 삭제 큐(FIFO) : 가장 먼저 들어온 데이터가 먼저 삭제 퀵 정렬 (Quick Sort)데이터들을 피벗(키)으로 부분적으로 나누어 가며 정렬하는 방법앞서 살펴본 정렬들과 달리 평균 시간복잡도는 O(n log n)이다. 최악 시간복잡도는 여전히 O(n^2) Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할프로그램을 Recall해야하므로 Stack 요구분할(Divide)와 정복(Conquer)을 활용 ex) 초기값 : 15 30 60 5 35 18예시에서는 가장 오른쪽 수인 18.. 2025. 6. 9.
[자료구조] 정렬 (sorting) - 버블 ,선택, 삽입, 쉘 알고리즘 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 정렬의 개념각 데이터를 특정 항목으로 오름차순 혹은 내림차순으로 재배열하는 작업을 말한다.정렬의 종류내부 정렬 : 삽입법, 교환법, 선택법, 병합법, 분배법 등 데이터량이 적을 때 RAM과 같은 주기억장치에 정렬하는 방법을 말한다.RAM은 속도가 빠른 대신에 용량이 작다. 외부 정렬 : 밸런스 병합 정렬, 캐스케이드 병합 정렬, 폴리파즈 병합 정렬, 오실레이팅 병합 정렬 대용량의 데이터를 HDD, SSD와 같은 보조기억장치에서 기억시켜서 정렬하는 방법을 말한다.내부정렬과는 반대로 속도가 느린 대신 용량이 크다. 컴퓨팅에서는 주기억장치가 내부 정렬 : 버블 정렬두 개의 데이터를 비교하여 크기에 따라 위치를 서로 .. 2025. 6. 5.

티스토리툴바