분류 전체보기 (154) 썸네일형 리스트형 자바에서의 정렬 Sorting in Java 기본 타입 데이터의 정렬- Arrays 클래스가 primitive 타입 데이터를 위한 메소드를 제공해준다.int[] data = new int[capacity];// data[0]에서 data[capacity - 1]까지 데이터가 꽉 차있을 경우Arrays.sort(data);//배열이 꽉 차지 않고 data[0]부터 data[size - 1]까지 차있을 경우Arrays.sort(data, 0, size);- int 이외 다른 primitive타입 데이터 (char, double 등)에 대해서도 같은 기능을 제공해준다. 객체의 정렬 - 문자열의 경우- primitive타입 데이터들과 같이 Arrays.sort메소드를 통해 쉽게 정렬이 가능하다.- 기본적으로 문자열은 Strin.. 선형시간 정렬 알고리즘 (2) 보호되어 있는 글입니다. 선형시간 정렬 알고리즘 (1) 선형 시간 정렬 알고리즘 (1) Counting Sort- n개의 정수를 정렬하는데, 모든 정수는 0에서 k사이의 정수라는 사전 지식이 주어지는 정렬법이기 때문에 크기관계만을 이용하여 정렬하지 않고 사전 지식을 적극적으로 활용한다. (k의 크기도 비교적 작은 편이다.)Ex) n명의 학생들의 시험점수를 정렬하라. 단 모든 정수는 100이하의 양의 정수이다.- k = 5인 경우A = 2 5 3 0 2 3 0 3 (n = 8)C(counter) = 2 0 2 3 0 1 => 각 인덱스마다 A배열에서 해당 수가 몇개 들어있는지 세어 저장한다.∴ A = 0 0 2 2 3 3 3 5- 슈도 코드int A[n];int C[k] = {0, };for (int i = 1; i 정렬의 하한점에 대해 정렬의 하한점 (Lower bound) 정렬 알고리즘의 유형- Comparison Sort데이터들 간의 상대적 크기관계만을 이용해 정렬하는 알고리즘따라서 데이터들 간의 크기 관계가 정의되어 있다면 어떤 데이터든 적용이 가능해진다. (문자열, 알파벳, 기타 따로 정의된 객체 등)버블 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등이 있다.- Non - Comparison Sort정렬할 데이터에 대한 사전지식을 이용한다. 하지만 이는 적용범위가 제한적이라는 한계가 있다.Bucket Sort와 Radix Sort가 대표적으로 알려져있는 정렬 방식이다. 정렬 문제의 최저점- 최저점 (Lower bound)입력된 데이터를 한번씩 다 보기 위해서 최소한 O(n)의 시간복잡도가 필요하다.합병 정렬과 힙 정렬 .. 힙의 응용 - 우선순위 큐 보호되어 있는 글입니다. 힙 정렬에 대해(2) 보호되어 있는 글입니다. 힙 정렬에 대해(1) 힙 정렬 (Heap Sort) Heap Sort- 최악의 경우 시간복잡도 O(n logn)- Sort in place -> 추가 배열이 필요하지 않다.- 이진 힙(binary heap) 자료구조를 사용하여 정렬을 수행한다. Heap의 정의- 조건1) complete binary tree이여야 한다.2) heap property를 만족해야 한다.- property는 아래 두 조건 중 하나를 만족해야 한다.1) Max heap property부모는 자식보다 크거나 같다2) Min heap property부모는 자식보다 작거나 같다. Full binary trees와 Complete binary trees- full binary trees모든 레벨에 노드들이 전부 차있는 상태의 트리이다.- complete b.. 정렬 알고리즘 - 퀵 정렬 퀵 정렬 (Quick Sort) 분할 정복법- 분할 : 배열을 아래의 조건이 되도록 두 부분으로 나눈다. (Pivot을 이용한다.)lower part elements ≤ upper part elements- 정복 : 각 부분을 순환적으로 정렬한다.- 합병 : 수행하지 않는다. 퀵 정렬 수행 과정- 정렬할 배열이 주어진다. 이 때 마지막 수를 기준 (pivot)으로 삼아둔다.31 8 48 73 11 3 20 29 65 15(pivot)- 기준보다 작은 수는 기준의 왼쪽에, 나머지는 기준의 오른쪽에 오도록 재배치 (분할)한다.8 11 3 15 31 48 20 29 65 73- 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다. 퀵 정렬 슈도 코드quickSort (A[], p, r) {if (p < r) {q.. 이전 1 ··· 12 13 14 15 16 17 18 ··· 20 다음
