Quicksort 알고리즘 (C#)

Question

이 코드에서 실제로 무엇이 잘못된지 묻고 싶습니다. 그래서 나는이 페이지에보고 혼자 퀵 (2 웨이)을 이해하려고 노력 : 나 자신에 의해 그것을 코드하려고 그 이후 http://me.dt.in.th/page/Quicksort/#disqus_thread 여기 도착 :

public void Sort(Comparison<TList> del, long l, long r) 
    { 
     // inspired by: http://me.dt.in.th/page/Quicksort/ 
     if (l >= r) return; 

     // partitioning 
     for(long i = l + 1; i <= r; i++) 
     { 
      if (del.Invoke(this[i], this[l]) < 0) 
      { 
       Swap(i, l); 
      } 
     } 

     // recursion 
     Sort(del, l, l - 1); 
     Sort(del, l + 1, r); 
    } 

그런 다음 제가 언급 한 웹 사이트에 댓글로 보았다

static void Main(string[] args) 
    { 
     MyList<int> obj; 

     do 
     { 
      obj = MyList.Random(100, 0, 100); 
      obj.Sort(stdc); 
      obj.Sort(stdc); 
     } while (obj.IsSorted(stdc)); 

     Log("Not sorted", obj); 

     Console.ReadKey(true); 
    } 

: (이 방법에 의해 링크 된 목록에 포함)이 함께 테스트

void qsort(char *v[], int left, int right) 
{ 
    int i, last; 
    void swap(char *v[], int i, int j); 

    if (left >= right) 
     return; 
    swap(v, left, (left + right)/2); 

    last = left; 

    for (i = left + 1; i <= right; i++) 
     if (strcmp(v[i], v[left]) < 0) 
      swap(v, ++last, i); 
    swap(v, left, last); 
    qsort(v, left, last - 1); 
    qsort(v, last + 1, right); 
} 

지금은 내 코드는 여전히 작동하는 이유 정말 궁금 :이 발견 이 :

public bool IsSorted(Comparison<TList> del) 
    { 
     var el = start; 

     if (el != null) 
     { 
      while (el.Next != null) 
      { 
       if (del.Invoke(el.Value, el.Next.Value) > 0) // eq. to this[i] > this[i + 1] 
        return false; 
       el = el.Next; 
      } 
     } 

     return true; 
    } 

을이 :

public static MyList<int> Random(int num, int min = 0, int max = 1) 
    { 
     var res = new MyList<int>(); 
     var rand = new Random(); 

     while (num > 0) 
     { 
      res.Add(rand.Next(min, max)); 
      num--; 
     } 

     return res; 
    } 

Answer 1

귀하의 퀵 코드는 정말 퀵하지 않고, 그 속도가 느려질 수 있습니다. (가) L> = (L-1)을 감지 호출로에 반복하기 때문에 라인

 Sort(del, l, l - 1); 

는 아무것도하지 않습니다. 라인

 Sort(del, l + 1, r); 

만에 의해 구획 [L, R]의 크기를 감소시킨다 [L + 1, R, 시간 복잡도는 항상 O 수 (N^2)하지만 같다 있도록 그것은 천천히 일할 것입니다.

qsort() 함수는 왼쪽과 중간 값을 서로 바꿉니다. 데이터가 이미 정렬되었지만 그 밖의 작업은 많이 수행하지 않으면 최악의 문제가 발생하지 않습니다. 핵심은 그것이 "last"를 업데이트하여 파티션이 완료되면 v [last]의 값이 피벗 값이 될 것이고 "left"대신 "last"를 사용하거나 코드 케이스에 재귀 호출을합니다 , "나".

표시된 qsort는 Lomuto 파티션 체계의 변형입니다.

https://en.wikipedia.org/wiki/Quicksort#Algorithm