외부 정렬(External Sort)이란? 데이터들의 크기가 주기억장치보다 커 정렬 할 데이터들을 주기억장치에 온전히 입력할 수 없는 경우 사용되는 정렬 방법을 의미한다. 예를 들어 주기억장치가 1GB고, 데이터 파일이 총 100GB라고 했을 때 내부 정렬 알고리즘을 사용하여 정렬할 수 없다. 외부 정렬 과정 분할 외부 정렬은 주기억장치에서 수용할 수 있는 데이터에 대해서만 읽어, 내부정렬을 수행 그 결과를 보조 기억 장치에 다시 저장한다. 여기서 내부 정렬은 상황에 맞는 정렬을 사용하면 된다. 1. 메모리 만큼 데이터를 읽어온다. 2. 활용할 내부 정렬을 이용하여 데이터를 정렬한다. 3. 정렬된 데이터를 보조 기억 장치에 기록한다. 정복 정렬되어 나눠진 블록들을 하나의 블록으로 만들기 위해 Merge ..

정렬 알고리즘 비교 Reference https://d2.naver.com/helloworld/0315536

https://programmers.co.kr/learn/courses/30/lessons/67258?language=java 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 정리 1. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 연속된 구간을 구하세요. 2. 만약 가장 짧은 연속된 구간이 여러개라면, 가장 왼쪽에 위치한 구간을 반환하세요. 3. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 구간은 무조건 1개 이상 존재합니다. 접근 방법 완전 탐색 이 문제는 우선 정확도 평가와 효율성 평가가 존재한다. 효율성 평가가 존재한다..

퀵 정렬의 개념 퀵정렬이란? 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 보인다. 하지만 역순으로 정렬되거나 이미 정렬된 데이터가 들어오면 비효율적이다.(불균형 분할이 일어남) 병합정렬과 다르게 똑같은 크기의 리스트로 나누는 것이 아닌, 피봇을 기준으로 리스트를 나누게 된다. 병합정렬은 배열을 우선 가장 작은 단위로 나눈 후에 데이터들이 정렬되는 반면에, 퀵 정렬은 데이터를 조건에 맞게 정렬 후 작은 단위로 나눈다. 동작 방식(오름차순 정렬) 리스트 안에 있는 한 요소를 피봇으로 선택한다. (정렬을 위한 기준이라고 보면 된다) 피봇을 기준으로 피봇보다 작은 요소들은 왼쪽으로, 피봇보다 큰 요소들은 피봇들의 오른쪽으로 옮겨진다. 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트에 대해서 각각 정..

병합 정렬의 개념 병합 정렬이란? 하나의 리스트를 두 개의 균등한 크기로 최대한 분할하고 분할된 부분 리스트를 순서대로 합하는 방식이다. 분할된 리스트를 순서대로 합쳐서 담기 위한 자료구조가 추가적으로 필요하다. 가장 작은 단위로 절반씩 쪼갠 후 가장 작은 단위부터 다시 합쳐나가는데 이 합쳐나가는 과정에서 데이터가 정렬이 된다. Divide and Conquer Merge Sort의 해결 전략 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 Divide and Conquer 방식은 대개 재귀 호출을 이용하여 구현함 동작 방식과 구현 1. 데이터들을 절반으로 나눈다. (분할) 2. 데이터를 가장 작은 단위로 분해한 후 맨 밑에서 부터 차례대로 합병을 진행..