단일 링크 목록의 quicksort

Question

내 quickSort가 작동하지 않습니다. 필자는 특히 분할 알고리즘을 통과해야하는 대상과 머리글 노드가되는 경우와 마지막 노드 인 경우와 같이 피벗을 관리하는 방법을 잘 모릅니다. 나는 배열에 대한 해결책에 대한 나의 접근 방식을 기반으로했다. 여기 내 시도가있다. 어떤 아이디어? 파티셔닝 알고리즘은 단일 링크 목록 (SLL)의 한 방향 특성에 맞게 선택되었습니다.

public static SLL quickSort(SLL list, SLLNode first, SLLNode last) 
{ 
    if (first != null && last != null) 
    { 
     SLLNode p = partition(list, first, last) ; 
     quickSort(list,first,p) ; 
     quickSort(list,p.succ, last) ; 
    } 
    return list ; 
} 

public static SLLNode partition(SLL list, SLLNode first, SLLNode last) 
{ 
    //last.succ = null ; 
    SLLNode p = first ; 
    SLLNode ptr = p.succ ; 

    while (ptr!=null) 
    { 
     if (ptr.data.compareToIgnoreCase(p.data)<0) 
     { 
      String pivot = p.data ; 
      p.data = ptr.data ; 
      ptr.data = p.succ.data ; 
      p.succ.data = pivot ; 
      p = p.succ ; 
     } 
     ptr = ptr.succ ; 
    } 
    return p ; 
} 

[편집]

• 나는 '자리에서'내가 특별히 머리를 관리하는 방법에 대한 도움말을 찾고

• 을이 작업을 수행 할 수 및이 과정에서 마지막 . 나의 접근 방식은

Answer 1

당신은 라인을 "last.succ = 널 (null)"체크 아웃 할 수 있습니다이 불가능 해입니다

제안하지 마십시오 대체하지 않는 한. 분할하는 목록 세그먼트의 끝에 도달했는지 확인하는 다른 방법을 찾고 싶을 것 같습니다. 그것이 그렇듯이, 여러분은 널 포인터 예외를 가져야한다고 생각합니다. 그러나 나는 오판 될 수 있습니다. 자바에 다음 의사 코드를 번역 비파괴 버전에 대한

Answer 2

:

quickSort list 
    | list.isEmpty = empty list 
    | otherwise = concat (quickSort lower) (new List(pivot, quickSort upper)) 
    where 
     pivot = list.head 
     lower = list of elements from list.tail that are < pivot 
     upper = list of elements from list.tail that are >= pivot 

Answer 3

연결리스트에 퀵에 대한 일반적인 접근 방식은 두 개 (또는 세 더 나은, 모든 요소가 동일하다면 가운데 하나를 만들 것 피벗 요소에 새 목록을 추가하고 첫 번째와 마지막을 재귀 적으로 정렬 한 다음 함께 연결합니다.

대신 코드가 노드 내부의 데이터를 교환합니다. 흥미 롭습니다. 나는 다음 (하위) 목록 그것을 시도 : 알고리즘이하는 무슨

 first       last 
     [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ] 

봐 :

 [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ] 
      p 
       ptr 

3<5? (yes) { 
pivot=5 
     [ 3 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ] 
      p  ptr 
     [ 3 ]-->[ 7 ]-->[ 7 ]-->[ 9 ]-->[ 2 ] 
      p  ptr 
     [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ] 
      p  ptr 
     [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ] 
        p 
       ptr 
} 
     [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ] 
        p 
         ptr 

이 첫 번째 반복 후 상태입니다. ptr != null부터 지금은 다음 반복을 진행하지만 이미 문제를 볼 수 있다고 생각합니다. 다음 반복 한 후에는 다음과 같습니다

 [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ] 
          p 
             ptr 

그리고 지금 우리 ptr.next == null 이후는, NullPointerException를 얻을 것이다 (또는이는의 하위 목록 인 경우

 [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ] 
          p 
           ptr 

를 다음 반복에서 더 스왑이 발생하지 더 큰 목록, 우리는 한계 밖에서 교환 할 것이다).

그래서, 몇 가지 아이디어 : 스와핑 단계

• , 당신은 확인해야합니다 이제 피벗 요소를 포함하는 노드 이후 p 점을 그.
• last 요소에 도달 할 때 중지해야하며, 필요하다면 요소 자체가 교체 된 후에도 교체하지 않아야합니다.

Answer 4

//logic - from left to right, remove smaller node and append at the beginning, 
public void partition(int x)// x is your pivot element. 
     { 
      Node prev = null; 
      Node cur = root; 
      while (cur!=null) 
      { 
       if (cur.data > x || cur == root) 
       { 
        cur = cur.next; 
        prev = cur; 
       } 
       else 
       { 
        Node next = cur.next; 
        if (prev != null) prev.next = next; 
        cur.next = root; 
        root = cur; 
        cur = next; 
       } 
      } 
     }