Talk:Sorting algorithm: Difference between revisions

Revision as of 03:00, 13 December 2015

Revision as of 03:04, 13 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 550 ⟶ 553:

</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 582 ⟶ 561:

::::: 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)

*UpdateOne -interesting aspect of this small loop is that if you consider sorting I addedby the values of A as a rotatepermutation, example.then this loop "unpermutes" I've, seenwhile thisat alsothe referredsame totime it "permutes" A. This occurs because the values in the locations swapped in I are used as mutatingindexes indicesfor the locations swapped in A. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 1023:0004, 1129 DecemberApril 20152013 (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 ==

Line 625 ⟶ 606:

:It doesn't seem like there is a reference supporting its position in the table, so if you have a good source that describes sorting networks as a strategy that can be applied to many different sorting algorithms, I think you could easily make that change. &ndash; [[User:FenixFeather|<font color="SlateBlue">'''''FenixFeather'''''</font>]] ^{[[User_talk:FenixFeather|<font color="SlateBlue">(talk)]]</font>}^{[[Special:Contributions/FenixFeather|<font color="SlateBlue">(Contribs)]]</font>} 04:34, 11 April 2014 (UTC)

There's an apparent error. Memory overhead should be 1, just a temp variable needed for the swaps. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 10:07, 11 December 2015 (UTC)

== Explanation of Comparison Sort methods ==