FilesExpand file tree

 main

/

P64_2.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

45 lines (40 loc) · 1.6 KB

 main

/

P64_2.java

Top

File metadata and controls

• Code
• Blame

45 lines (40 loc) · 1.6 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package ch17;

import datatype.ListNode;

public class P64_2 {

public void quicksort(ListNode head, ListNode tail) {

// 단일 노드일때는 그냥 리턴

if (head == tail) return;

// 연결 리스트이기 때문에 로무토 파티션이 아닌 편의상 첫 번째 노드를 피벗으로 선택

ListNode pivot = head;

// 왼쪽 포인터는 첫 번째 노드

ListNode left = head;

// 오른쪽 포인터는 그다음 노드

ListNode right = head.next;

// 오른쪽 포인터가 맨 끝에 도달할 때까지 진행

while (right != tail) {

if (right.val < pivot.val) {

// 왼쪽 포인터 진행

left = left.next;

// 스왑, 연결 리스트이므로 노드 처리를 단순하게 하기 위해 값만 교환

int temp = left.val;

left.val = right.val;

right.val = temp;

}

// 오른쪽 포인터 진행

right = right.next;

}

// 피벗과 왼쪽 포인터 값 교환, 피벗은 첫 번째 노드

int temp = head.val;

head.val = left.val;

left.val = temp;

// 왼쪽 포인터를 중심으로 분할하여 재귀 호출

quicksort(head, left);

quicksort(left.next, tail);

}

public ListNode sortList(ListNode head) {

// 연결 리스트의 마지막은 널이므로 tail을 null로 하여 호출

quicksort(head, null);

// 정렬이 끝나면 첫 번째 노드인 head를 결과로 리턴

return head;

}

}