티스토리 뷰
정렬
1. 병합정렬
2. 퀵정렬
* 삽입 정렬? 정렬을 해야할 대상, 정렬을 끝낸 대상 -> 두 그룹으로 나누어 진행
* cur -> 정렬을 끝낸 연결 리스트 추가, 이미 정렬을 끝냈기 때문에
* parent -> 계속 그 위치에 두어 사실상 루트를 가리키게 함
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = parent = ListNode(0);
while head:
while cur.next and cur.next.val < head.val:
cur = cur.next
cur.next, head.next, head = head, cur.next, head.next;
if head and cur.val > head.val:
cur = parent
return parent.next
- 단순하게 dfs를 사용해서 정렬
(1) dfs 사용해서 푼 답 -> Time Error
class Solution:
def largestNumber(self, nums: List[int]) -> str:
def dfs(_route, _num):
if len(_num) == 0:
result.append(int(_route))
return;
for i in range(0,len(_num)):
dfs(_route + str(_num[i]), _num[:i] + _num[i+1:])
result = [];
dfs('',sorted(nums))
return str(sorted(result)[-1])(2)
for i in range(0,len(nums)):
for j in range(i+1,len(nums)):
if str(nums[i]) + str(nums[j]) < str(nums[j]) + str(nums[i]):
nums[i], nums[j] = nums[j], nums[i]
result = [str(x) for x in nums]
return str(int(''.join(result)))
973. K Closest Points to Origin
* java
2. 정렬
- 데이터를 왜 정렬해야할까? 탐색을 위해서
- 단순하지만 비효율적인 방법 -> 버블정렬, 선택정렬, 삽입정렬
- 복잡하지만 효율적인 방법 -> 퀵정렬, 힙정렬, 합병정렬, 기수정렬
- 공통문제 -> int[] values = {4,3,6,8,23,2,35,7,248,2,3,45};
다음과 같은 values를 사용하여 버블정렬, 선택정렬 하기소
2.1 버블정렬(Bubble Sort) - $O(n^2)$
- 1번째와 2번째 원소 비교 정렬, ... , n-1번째와 n번째를 정렬하는 코드
- 이해하기 쉽고, 코드가 짧음 , 입력량이 작으면 많이 비효율적이지 않지만 버블 정렬은 양이 많으면 효율이 없음
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int[] bubbles = {4,3,6,8,23,2,35,7,248,2,3,45};
int dummy;
for(int i=0 ; i<bubbles.length ; i++ ){
for(int j=0 ; j <bubbles.length-i-1 ; j++ ){
if(bubbles[j] > bubbles[j+1]){
dummy = bubbles[j];
bubbles[j] = bubbles[j+1];
bubbles[j+1] = dummy;
}
}
}
for(Integer bubble:bubbles)
System.out.println(bubble);
|
cs |
2.2 선택 정렬(Selection Sort) - $O(n^2)$
- 제자리 정렬 알고리즘 중 하나, 다음과 같은 순서로 이루어짐
(1) 주어진 리스트 중에 최소값을 찾기
(2) 그 값을 맨 앞에 위치한 값과 교체하기
(3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체
- 장점 -> 자료 이동 횟수가 미리 결정
- 단점 -> 안정성 만족, 상대적인 위치 변동 가능
2.3 삽입 정렬(Insertion Sort) - $O(n^2)$
- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽임함으로써 정렬을 완성하는 알고리즘
2.4 힙 정렬(Heap Sort)
- 힙의 개념을 이용하여 정렬하는 알고리즘
- 주어진 자료를 기반으로 힙을 구성, 큰수에서 작은수로 정렬하려면 주어진 자료를 이용하여 최상위 데이터를 가장 큰수로 설정
- 최상위 데이터를 빼면 나머지 데이터로 다시 힙 구성
2.5 퀵 정렬(Quick Sort)
- 중앙값 정렬 방식을 확장해서 개발한 방식
- 임의로 선정된 데이터 중심으로 데이터 2등분, 각 분리된 부분의 첫번째 원소 기준으로 데이터 분리
<출처 - 그림으로 정리한 알고리즘과 자료구조>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class QuickSortclass {
public static void main(String args[]){
Integer[] array = {30,50,7,40,88,15,44,55,22,33,77,99,11,66,1,85};
ArrayList<Integer> aList = new ArrayList<Integer>();
aList.addAll(Arrays.asList(array));
aList = (ArrayList<Integer>) quicksort(aList);
System.out.println(aList.toString());
//out.print(aList.toString());
}
public static <T extends Comparable<? super T>> List<T> quicksort(List<T> list){
if(list.size() <= 1) return list;
int pivot = list.size() /2 ;
List<T> a = new ArrayList<T>();
List<T> b = new ArrayList<T>();
int c = 0;
for(T number : list){
if(list.get(pivot).compareTo(number) < 0)
b.add(number);
else if(list.get(pivot).compareTo(number) > 0)
a.add(number);
else
c++;
}
a = quicksort(a);
for(int i=0 ; i<c ; i++)
a.add(list.get(pivot));
b = quicksort(b);
List<T> sorted = new ArrayList<T>();
sorted.addAll(a);
sorted.addAll(b);
return sorted;
}
}
|
cs |
2.6 합병정렬(Merge Sort)
- 데이터를 분할 한 다음 각자 계산하고 나중에 합쳐서 정렬하는 알고리즘
2.7. 기수정렬 (... )
3. Interface Comparable & Interface Comparator
(1) Interface Comparable
- 객체간의 일반적인 정렬이 필요할 때. compareTo
- package: java.lang.Comparable
|
1
2
3
|
public interface Comparable<T> {
int compareTo(T var1);
}
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
class Students implements Comparable<Students>{
private int id;
private String name;
private String department;
@Override
public String toString() {
return "Students{" +
"id=" + id +
", name='" + name + '\'' +
", department='" + department + '\'' +
'}';
}
public Students(int id, String name, String department) {
this.id = id;
this.name = name;
this.department = department;
}
@Override
public int compareTo(Students o) {
//return this.name.compareTo(o.name);
return this.id - o.id;
}
}
public class QuickSortclass {
public static void main(String args[]) {
Students student0 = new Students(4,"Rose","D");
Students student1 = new Students(2,"Jenny","B");
Students student2 = new Students(1,"Lisa","A");
Students student3 = new Students(3, "Jisu","C");
List<Students> student = new ArrayList<>();
student.add(student0);
student.add(student1);
student.add(student2);
student.add(student3);
System.out.println(student);
/*
[Students{id=4, name='Rose', department='D'}, Students{id=2, name='Jenny', department='B'},
Students{id=1, name='Lisa', department='A'}, Students{id=3, name='Jisu', department='C'}]
*/
Collections.sort(student);
System.out.println(student);
/*
[Students{id=1, name='Lisa', department='A'}, Students{id=2, name='Jenny', department='B'},
Students{id=3, name='Jisu', department='C'}, Students{id=4, name='Rose', department='D'}]
*/
}
}
|
cs |
(2) Interface Comparator
- 객체간의 특정한 정렬이 필요할때, compare() Method
- 정렬가능한 클래스와 달리 기본 정렬 기준과 다르게 정렬하고 싶을때
- package: java.util.Comparator
<여기>
Comparator을 사용하는 방법, 위는 람다함수로 사용한 것이고 아래는 익명클래스로 사용한 것이다. 람다함수로 사용하니 더욱 더 간편하게 사용할 수 있었으며, 익명 클래스 사용지 조금 복잡한 감을 보인다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
Comparator<Students> Comp = (o1,o2) -> (o1.id - o2.id);
Comparator<Students> Comp2 = new Comparator<Students>() {
@Override
public int compare(Students a, Students b) {
// TODO Auto-generated method stub
return a.id - b.id;
}
};
|
cs |
<전체코드 - 익명함수 사용>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
import java.util.*;
class Students {
public int id;
public String name;
public String department;
@Override
public String toString() {
return "Students{" +
"id=" + id +
", name='" + name + '\'' +
", department='" + department + '\'' +
'}';
}
public Students(int id, String name, String department) {
this.id = id;
this.name = name;
this.department = department;
}
}
public class QuickSortclass {
public static void main(String args[]) {
Students student0 = new Students(4,"Rose","D");
Students student1 = new Students(2,"Jenny","B");
Students student2 = new Students(1,"Lisa","A");
Students student3 = new Students(3, "Jisu","C");
List<Students> student = new ArrayList<>();
student.add(student0);
student.add(student1);
student.add(student2);
student.add(student3);
System.out.println(student);
/*
[Students{id=4, name='Rose', department='D'}, Students{id=2, name='Jenny', department='B'},
Students{id=1, name='Lisa', department='A'}, Students{id=3, name='Jisu', department='C'}]
*/
Comparator<Students> Comp = (o1,o2) -> (o1.id - o2.id);
Comparator<Students> Comp2 = new Comparator<Students>() {
@Override
public int compare(Students a, Students b) {
// TODO Auto-generated method stub
return a.id - b.id;
}
};
Collections.sort(student,Comp2);
System.out.println(student);
/*
[Students{id=1, name='Lisa', department='A'}, Students{id=2, name='Jenny', department='B'},
Students{id=3, name='Jisu', department='C'}, Students{id=4, name='Rose', department='D'}]
*/
}
}
|
cs |
<전체코드 - 클래스 생성해서 정직하게>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
class Students implements Comparator<Students> {
public int id;
public String name;
public String department;
@Override
public String toString() {
return "Students{" +
"id=" + id +
", name='" + name + '\'' +
", department='" + department + '\'' +
'}';
}
public Students(){
}
public Students(int id, String name, String department) {
this.id = id;
this.name = name;
this.department = department;
}
@Override
public int compare(Students o1, Students o2) {
return o1.id - o2.id;
}
}
public class QuickSortclass {
public static void main(String args[]) {
Students student0 = new Students(4,"Rose","D");
Students student1 = new Students(2,"Jenny","B");
Students student2 = new Students(1,"Lisa","A");
Students student3 = new Students(3, "Jisu","C");
List<Students> student = new ArrayList<>();
student.add(student0);
student.add(student1);
student.add(student2);
student.add(student3);
System.out.println(student);
/*
[Students{id=4, name='Rose', department='D'}, Students{id=2, name='Jenny', department='B'},
Students{id=1, name='Lisa', department='A'}, Students{id=3, name='Jisu', department='C'}]
*/
Collections.sort(student, new Students());
System.out.println(student);
/*
[Students{id=1, name='Lisa', department='A'}, Students{id=2, name='Jenny', department='B'},
Students{id=3, name='Jisu', department='C'}, Students{id=4, name='Rose', department='D'}]
*/
}
}
|
cs |
<출처>
1. ko.wikipedia.org/wiki/힙_(자료_구조)
3. 선택정렬 - ko.wikipedia.org/wiki/선택_정렬
4. gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
5. docs.oracle.com/javase/8/docs/api/
6. www.youtube.com/watch?v=ltCQVpQtTiw
7. www.geeksforgeeks.org/comparator-interface-java/
8.
'Programming > 자료구조' 카테고리의 다른 글
| [자료구조] 힙 (0) | 2022.05.03 |
|---|---|
| [자료구조/코테] 그래프 (0) | 2022.05.03 |
| [자료구조] Queue & Stack (0) | 2022.04.02 |
| [자료구조/코테] Hash Table (0) | 2022.03.01 |
| [자료구조/코테] Math (0) | 2022.03.01 |