Проблема с моей быстрой сортировкой, она не сортируется правильно

Question

ОК. Я пытаюсь создать алгоритм Prima, поэтому мне нужно отсортировать массив ребер, я попытался использовать здесь быструю сортировку, но это не сработало, как я планировал.

#include <iostream>


using namespace std;

void Sort (int arr[100][4], int m, int l) {
     int i,j,x,v;

    i=m;
    j=l;
    x=(i+j)/2;
    do
    {
        while (((arr[i][3]<arr[x][3]))and(i<=l)) i++;
        while (((arr[j][3]>arr[x][3]))and(j>=m)) j--;
        if (i<=j)
        {
        v=arr[i][1];
        arr[i][1]=arr[j][1];
        arr[j][1]=v;
        v=arr[i][2];
        arr[i][2]=arr[j][2];
        arr[j][2]=v;
        v=arr[i][3];
        arr[i][3]=arr[j][3];
        arr[j][3]=v;
        i++;
        j--;
        }
    }
    while (i<=j);
    if (i<l) Sort(arr,i,l);
    if (m<j) Sort(arr,m,j);
}

int main () {
    int i,x,y,z,n,m;
    int a[100][4];
    fill(&a[0][0],&a[0][0]+400,0);
    cout<<"Enter number of nodes and edges\n";
    cin>>n>>m;
    cout<<"Enter edges and their weights\n";
    for (i=0;i<m;i++) {
        cin>>x>>y>>z;
        a[i][1]=min(x,y);
        a[i][2]=max(x,y);
        a[i][3]=z;
        }
    Sort (a,0,m-1);
    for (i=0;i<m;i++) {
        cout<<i+1<<") "<<a[i][1]<<' '<<a[i][2]<<' '<<a[i][3]<<endl;
    }
    return 0;
}

что я положил это

5 10

1 2 4

1 3 7

4 1 5

5 1 8

2 3 3

2 4 6

2 5 6

3 4 8

3 5 2

4 5 4

что я получаю 1) 3 5 2

2) 2 3 3

3) 1 4 5

4) 1 2 4

5) 4 5 4

6) 2 5 6

7) 2 4 6

8) 1 3 7

9) 1 5 8

10) 3 4 8

Я не понимаю, почему 5 опережает 4. Надеюсь, вы могли бы помочь.

Answer 1

Измените код, чтобы использовать сводное значение вместо сводного индекса и некоторые исправления, чтобы сделать его более похожим на обычную схему разбиения Hoare:

    i=m-1;
    j=l+1;
    x=arr[(i+j)/2][3];
    while(1)
    {
        while (arr[++i][3] < x);
        while (arr[--j][3] > x);
        if(i >= j)
            return j;
        // ...

Answer 2

Вы выбираете элемент pivot в середине (под) массива, что нормально, но вы оставляете его в этой позиции при запуске цикла разбиения и полагаетесь на него до оставайтесь там, что не в порядке.При вашем подходе шарнир, вероятно, будет переставлен в другую позицию во время обычного хода секционирования, после чего оставшаяся часть секционирования будет основана на ключе, переведенном в исходное положение шарнира, которое, вероятно, будет другим.

Обычный подход состоит в том, чтобы начать с перестановки элемента pivot на один конец массива или другого, разбить оставшуюся часть массива, а затем затем переставить pivot в правильное положение, как было обнаружено в процессе разделения.