Быстрая сортировка с первым элементом в качестве примера поворота

Question

Я сейчас изучаю быструю сортировку и хотел бы знать, как она работает, когда в качестве точки поворота выбран первый (или последний) элемент.

Скажем, например, у меня есть следующий массив:

{15, 19, 34, 41, 27, 13, 9, 11, 44}

Вот что я думаю:

{15, 19, 34, 41, 27, 13, 9, 11, 44}
 ^
pivot

{15, 19, 34, 41, 27, 13, 9, 11, 44}
 ^                              ^
compare these two, they are good

{15, 19, 34, 41, 27, 13, 9, 11, 44}
 ^                          ^
compare these two and swap

{11, 19, 34, 41, 27, 13, 9, 15, 44}
 ^                       ^
compare these two and swap

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^                  ^
compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^              ^
 compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^          ^
compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^      ^
 compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^  ^
 compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}

End of first partition

Так ли это работает?Если это так, будет ли новая точка опоры 19, или вы разделите массив пополам, чтобы найти его (чтобы он был 27/13), или это будет зависеть от реализации быстрой сортировки?Спасибо за ваше время!

Answer 1

Проверьте википедию, есть небольшой пример с немного меньшим списком быстрой сортировки на месте http://en.wikipedia.org/wiki/Quicksort

На вашем примере идея состоит в разбиении

{15, 19, 34, 41, 27, 13, 9, 11, 44}

в

{13, 9, 11 -- 15 -- 19, 34, 41, 27, 44}

Итак, сначала мы переместим пивот к концу

Swap 44, and 15
{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^                          ^

Than check 44, its larger than pivot, so swap with one one before last...

{11, 19, 34, 41, 27, 13, 9, 44, 15}
 ^                       ^

than check element at some position as last one was larger than pivot.
9 < 15, so proceed to the next, 19 > 15 => swap

{11, 9, 34, 41, 27, 13, 19, 44, 15}
        ^            ^

swap again
{11, 9, 13, 41, 27, 34, 19, 44, 15}
        ^       ^

next
{11, 9, 13, 41, 27, 34, 19, 44, 15}
            ^   ^

and second last swap

{11, 9, 13, 27, 41, 34, 19, 44, 15}
            ^    

Now as forward and backward indices reached each other,
we swap pivot into right position

{11, 9, 13, 15, 41, 34, 19, 44, 27}

И мы получили множество разделов. Позиции меньше 15 в начале, чем пивот = 15, а затем элементы большего размера.

РЕДАКТИРОВАТЬ: алгоритм, описанный в статье в Википедии, немного отличается:

Legend:
^ = storeindex
# = i

{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^#

{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^   #

... until ...   

{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^                   #

{13, 19, 34, 41, 27, 44, 9, 11, 15}
     ^                   #

{13, 9, 34, 41, 27, 44, 19, 11, 15}
        ^                   #

{13, 9, 11, 41, 27, 44, 19, 34, 15}
            ^                   #

{13, 9, 11, 15, 27, 44, 19, 34, 41}
            ^- pivot

Answer 2

https://www.youtube.com/watch?v=COk73cpQbFQ для последнего элемента как пивот

int partition(int *a,int start,int end)

{

int pivot=a[end],temp,p1=start,i;

for(i=start;i<end;i++)
{
    if(a[i]<pivot)
    {
        if(i!=p1)
        {
            temp=a[p1];
            a[p1]=a[i];
            a[i]=temp;
        }
        p1++;
    }
}

        temp=a[p1];
        a[p1]=a[end];
        a[end]=temp;
return p1;
}

https://www.youtube.com/watch?v=6UHCG64tHgo для первого элемента как пивот

 int partition1(int *a,int start,int end)

{

int pivot=a[start],p1=start+1,i,temp;

for(i=start+1;i<=end;i++)
{

if(a[i]<pivot)
    {
        if(i!=p1)
      {  
            temp=a[p1];
            a[p1]=a[i];
            a[i]=temp;
      }    p1++;
    }
}

        a[start]=a[p1-1];
        a[p1-1]=pivot;

return p1-1;
}




  void quicksort(int *a,int start,int end)
{
 int p1;
 if(start<end)
{
    p1=partition(a,start,end);
    quicksort(a,start,p1-1);
    quicksort(a,p1+1,end);
}
}

Answer 3

Попробуйте этот алгоритм: https://www.youtube.com/watch?v=7h1s2SojIRw

Основная идея: все элементы слева меньше, чем все элементы справа, тогда элемент считается «отсортированным».

Алго:

// partition
 Partition(l,h) {
     pivot = A[l];
     i=l; j=h;

     while(i<j) {
         do {
             i++;
         } while(A[i]<=pivot);

         do {
             j--;
         } while(A[j]>pivot);

         if(i<j) {
             swap(i,j);
         }
     }

     swap(A[l], A[j]);

     return j;
 }

 // quicksort
 QuickSort(l,h) {
     pi = Partition(l, h);
     QuickSort(l, pi);
     QuickSort(pi+1, h);
 }

Answer 4

Выбор первого элемента в качестве оси ...

class QuickSortPart1{
    public int partition(int[] a, int left, int right) {
        int pivot = a[left];
        while(left<=right) {
            while(a[left] < pivot)
                left++;
            while(a[right] > pivot)
                right--;
            if(left<=right) {
                int tmp = a[left];
                a[left] = a[right];
                a[right] = tmp;
                left++;
                right--;
            }
        }
        return left;
    }
    public void recursiveQuickSort(int[] a, int i, int j) {
       int idx = partition(a, i, j);
       if(i < idx-1) {
           recursiveQuickSort(a, i, idx-1);
        }
       if(j > idx) {
           recursiveQuickSort(a, idx, j);
        }
    }

    void printarray(int arr[]){
        int len = arr.length;
        for(int i=0; i<len; i++)
            System.out.print(arr[i]+" ");
    }
    public static void main(String[] args) {
        int arr[] = new int[]{5,8,1,3,7,9,2};
            System.out.print(arr[i]+" ");
        System.out.println("\n");
        QuickSortPart1 ob = new QuickSortPart1();
        ob.recursiveQuickSort(arr, 0, arr.length-1);
        ob.printarray(arr);
    }
}

Answer 5

/* Quick Sort taking first element as pivot element*/
void QuickSort(int* arr,int start,int last)
 {
     int i=start+1,j=last,temp;
     if(i>j)
     return;
     while(i<=j)
     {
              if(arr[i]<arr[start])
              {enter code here
                               i++;
              }
              if(arr[j]>arr[start])
              {
                               j--;                
              }
              if(i<=j)
              {
                  temp=arr[i];
                  arr[i]=arr[j];
                  arr[j]=temp;
              }
      }

       temp=arr[start];
       arr[start]=arr[j];
       arr[j]=temp;

       QuickSort(arr,start,j-1);
       QuickSort(arr,j+1,last);
}

для посещения всего кода: - http://www.liladharpaliwal.blogspot.in/

Answer 6

the following code uses first element as pivot

public static int[] qs(int[] list, int start, int end) {
if (end - start <= 1) {
  return list;
}
int pivot = split(list, start, end);   
qs(list, start, pivot);
qs(list, pivot + 1, end);
return list;
}

private static int split(int[] list, int start, int end) {
int pivot = list[start];
int i = start;
for (int j = start + 1; j <= end; j++) {
  int current = list[j];
  if (current < pivot) {
    swap(list, i + 1, j);
    i++;
  }
}
swap(list, start, i);
return i;
}

private static void swap(int[] list, int i, int j) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}