퀵 정렬 pivot값을 잡아  피벗의 왼쪽에는 피벗보다 작은값만 모여있도록 ,피벗의 오른쪽에는 피벗보다 큰 값만 모여있도록 pivot의 위치를 조정한다. 이렇게해서 왼쪽 파티션에대해 quick정렬을 다시 수행하고오른쪽 파티션에대해 quick정렬을 수행해 재귀적으로 정렬하는방식. 일반적으로 피벗의 값은 배열의 맨첫부분, 중간부분 , 맨 뒷부분을 사용한다. 나는 배열의 맨 첫부분을 피벗의 인덱스 값으로 잡았다.   구현  package Algorithm;import java.util.Arrays;public class Sort_Quick { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = { 1,..

병합 정렬 자료를 최소 단위까지 나눈 후 차례대로 정렬하여 최종 결과를 도출 해 내는 분할 정복 (divide and conquer) 방식 큰 단위 부터 최소 단위까지 쪼개기때문에 Top-down 방식이라고 불리며 병합 정렬같은 경우 2가지 case로 쪼개기때문에 2-way Top-down 방식이라고 불린다 연결리스트 방식이 가장 효율적임  시간 복잡도 이진트리의 높이는 log N , 정렬 시  최대 N번의 정렬과정을 거치므로시간복잡도는 O(n log n)  장점최악의 케이스에 상관없이 항상 시간복잡도 O(n log n)을 보장함.같은 값을 가지는 원소들의 정렬 순서가 정렬 후에도 변함이 없는 안정 정렬(Stable Sort)이다.단점 추가적으로 메모리를 필요로하기 때문에 제자리 정렬(In-place S..

삽입 정렬도서관 사서가 책을 정리하는 방식과 유사자료를 하나꺼내 앞에서부터 비교하며 자료가 들어갈 곳을 탐색 하는 방식 삽입 정렬 과정 정렬 할 자료를 두 부분집합 S와 U로 가정      - 부분집합 S : 앞쪽의 정렬된 부분 집합      - 부분집합 U : 정렬되지 않은 부분 집합 정렬 되지 않은 집합 U에서 원소를 하나씩 꺼내어 S의 마지막 원소부터 비교하여 S의 적합한 자리에 삽입한다. 삽입 정렬을 계속 수행하면 S의 원소는 1씩 증가하고, U의 원소는 1씩 감소한다 U가 공집합이 되면 정렬이 완료.   시간 복잡도Best Case : 모두 정렬되어 있을때 외부 루프: (n - 1)번내부 루프 : 이동 없이 1번만 수행. Best Case = O(n)Worst Case : 역순 정렬 되어있을때 ..

버블 정렬1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째까지다시 처음으로 돌아가 이번에는 n-3번째와 n-2번째까지... 를   총 (n-1)번 반복한다.   굉장히 직관적이고 구현하기 쉬운 코드이지만 매우 비효율적인 정렬방식으로 실제로는 거의 사용되지 않는 정렬방식이다. 장점이 구현하기 쉽다는것이 전부인 알고리즘  시간복잡도는 O(n^2) 구현for(int i = arr.length - 1 ; i > 0; i--) { for(int j = 0 ; j arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j+ 1] = tmp; ..