Talk:Sorting algorithm: Difference between revisions

Revision as of 04:45, 11 December 2015

Revision as of 10:00, 11 December 2015

Line 522:

int i;

for(i = 0; i < n; i++)

while( a[i] != a[a[ i]] )

swap(a[i], a[a[i]]);

}

Line 535:

// A is an array of size n

A[] = ... ;

// generate array of indexes I

for(i = 0; i < n; i++)

I[i] = i;

// sort I based on values in A

sort(I, A);

// sort A using the sorted list of indexes in I

// while also sorting I

for(i = 0; i < n; i++){

while( I[i] != I[I[ i]] ){

swap(A[I[i]], A[I[I[i]]]);

swap( I[i], I[I[i]] );

Line 553 ⟶ 550:

</source>

[[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 01:04, 29 April 2013 (UTC)

C++ example using rotates instead of swaps.

<source lang="C">

// create array of indices to A[]

for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)

I[i] = i;

// sort array of indices to A[] (lambda compare)

std::sort(I, I+sizeof(I)/sizeof(I[0]),

[&A](size_t i, size_t j){return A[i] < A[j];});

// reorder A[] according to I[]

for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){

if(i != I[i]){

tA = A[i];

k = i;

while(i != (j = I[k])){

A[k] = A[j];

I[k] = k;

k = j;

}

A[k] = tA;

I[k] = k;

}

}

</source>

::: [[Cycle sort]] would seem like an appropriate name, but it has already been taken, although it does seems to be based on the same underlying principle: "It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result." I wouldn't be surprised if this sort doesn't have a name, as it seems to be mostly of theoretical interest: with the given preconditions it shouldn't be too hard to keep the list sorted in memory in the first place. The extension of the sort to work on key-value pairs can be applied to any sorting algorithm. —''[[User:Ruud Koot|Ruud]]'' 17:10, 29 April 2013 (UTC)

Line 561 ⟶ 582:

::::: Most [[in-place sorting algorithm]]s, including [[bubble sort]] and [[quicksort]], work by swapping elements. This specific algorithm, though, goes through each [[cycle (mathematics)|cycle]] in the permutation one-at-a-time. Thus the number of iterations of the for-loop in which you perform at least one iteration of the nested while-loop is always exactly equal to the number of cycles in the permutation. —''[[User:Ruud Koot|Ruud]]'' 11:54, 30 April 2013 (UTC)

*OneUpdate interesting aspect of this small loop is that if you consider sorting- I by the values of A asadded a permutation,rotate then this loop "unpermutes"example. I,'ve whileseen atthis thealso samereferred time it "permutes" A. This occurs because the values in the locations swapped in I are usedto as indexesmutating for the locations swapped in A.indices [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 2310:0400, 2911 AprilDecember 20132015 (UTC)

::So the main enhancement of this algorithm is the part that sorts the array A[] while performing the special cycle sort on I[]. I searched again but wasn't able to to fing any references citing that special cycle sort could be used for this purpose. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 04:01, 1 May 2013 (UTC)

== Adding explanation for in-place sort ==