Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 8625032

Browse files
committed
OddEvenSort, OddEvenSortTest, SimpleDemo, SortDemo: Added new sorting algorithm.
1 parent 9297164 commit 8625032

File tree

4 files changed

+113
-0
lines changed

4 files changed

+113
-0
lines changed
Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
/*
2+
* Sorting algorithms demo (Java)
3+
*
4+
* Copyright (c) Project Nayuki
5+
* https://www.nayuki.io/page/sorting-algorithms-demo-java
6+
*
7+
* (MIT License)
8+
* Permission is hereby granted, free of charge, to any person obtaining a copy of
9+
* this software and associated documentation files (the "Software"), to deal in
10+
* the Software without restriction, including without limitation the rights to
11+
* use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
12+
* the Software, and to permit persons to whom the Software is furnished to do so,
13+
* subject to the following conditions:
14+
* - The above copyright notice and this permission notice shall be included in
15+
* all copies or substantial portions of the Software.
16+
* - The Software is provided "as is", without warranty of any kind, express or
17+
* implied, including but not limited to the warranties of merchantability,
18+
* fitness for a particular purpose and noninfringement. In no event shall the
19+
* authors or copyright holders be liable for any claim, damages or other
20+
* liability, whether in an action of contract, tort or otherwise, arising from,
21+
* out of or in connection with the Software or the use or other dealings in the
22+
* Software.
23+
*/
24+
25+
package io.nayuki.sortalgodemo.algo;
26+
27+
import io.nayuki.sortalgodemo.core.SortAlgorithm;
28+
import io.nayuki.sortalgodemo.core.SortArray;
29+
30+
31+
/**
32+
* Sorts by scanning forward and swapping inverted adjacent elements.
33+
* <ul>
34+
* <li>Time complexity, best case: &#x398;(<var>n</var>).</li>
35+
* <li>Time complexity, average case: &#x398;(<var>n</var><sup>2</sup>).</li>
36+
* <li>Time complexity, worst case: &#x398;(<var>n</var><sup>2</sup>).</li>
37+
* <li>Number of comparisons, best case: &#x398;(<var>n</var>).</li>
38+
* <li>Number of comparisons, average case: &#x398;(<var>n</var><sup>2</sup>).</li>
39+
* <li>Number of comparisons, worst case: &#x398;(<var>n</var><sup>2</sup>).</li>
40+
* <li>Number of swaps, best case: &#x398;(1).</li>
41+
* <li>Number of swaps, average case: &#x398;(<var>n</var><sup>2</sup>).</li>
42+
* <li>Number of swaps, worst case: &#x398;(<var>n</var><sup>2</sup>).</li>
43+
* <li>Auxiliary space complexity, all cases: &#x398;(1).</li>
44+
* </ul>
45+
*/
46+
public final class OddEvenSort implements SortAlgorithm {
47+
48+
// Singleton
49+
public static final SortAlgorithm INSTANCE = new OddEvenSort();
50+
51+
52+
private OddEvenSort() {}
53+
54+
55+
@Override public String getName() {
56+
return "Odd-even sort";
57+
}
58+
59+
60+
/*---- Algorithm ----*/
61+
62+
@Override public void sort(SortArray array) {
63+
while (true) {
64+
boolean changed = false;
65+
for (int i = 0; array.length() - i >= 2; i += 2)
66+
changed |= array.compareAndSwap(i, i + 1);
67+
for (int i = 1; array.length() - i >= 2; i += 2)
68+
changed |= array.compareAndSwap(i, i + 1);
69+
if (!changed)
70+
break;
71+
}
72+
}
73+
74+
}

‎src/io/nayuki/sortalgodemo/simple/SimpleDemo.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ public final class SimpleDemo {
4242

4343
BubbleSort.INSTANCE,
4444
CocktailSort.INSTANCE,
45+
OddEvenSort.INSTANCE,
4546
SelectionSort.INSTANCE,
4647
GnomeSort.INSTANCE,
4748
InsertionSort.INSTANCE,

‎src/io/nayuki/sortalgodemo/visual/SortDemo.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@ public static void main(String[] args) {
5050
// Approximately O(n^2) (mediocre)
5151
BubbleSort.INSTANCE,
5252
CocktailSort.INSTANCE,
53+
OddEvenSort.INSTANCE,
5354
SelectionSort.INSTANCE,
5455
CycleSort.INSTANCE,
5556
PancakeSort.INSTANCE,
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/*
2+
* Sorting algorithms demo (Java)
3+
*
4+
* Copyright (c) Project Nayuki
5+
* https://www.nayuki.io/page/sorting-algorithms-demo-java
6+
*
7+
* (MIT License)
8+
* Permission is hereby granted, free of charge, to any person obtaining a copy of
9+
* this software and associated documentation files (the "Software"), to deal in
10+
* the Software without restriction, including without limitation the rights to
11+
* use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
12+
* the Software, and to permit persons to whom the Software is furnished to do so,
13+
* subject to the following conditions:
14+
* - The above copyright notice and this permission notice shall be included in
15+
* all copies or substantial portions of the Software.
16+
* - The Software is provided "as is", without warranty of any kind, express or
17+
* implied, including but not limited to the warranties of merchantability,
18+
* fitness for a particular purpose and noninfringement. In no event shall the
19+
* authors or copyright holders be liable for any claim, damages or other
20+
* liability, whether in an action of contract, tort or otherwise, arising from,
21+
* out of or in connection with the Software or the use or other dealings in the
22+
* Software.
23+
*/
24+
25+
package io.nayuki.sortalgodemo.algo;
26+
27+
import io.nayuki.sortalgodemo.core.FastSortAlgorithmTest;
28+
import io.nayuki.sortalgodemo.core.SortAlgorithm;
29+
30+
31+
public final class OddEvenSortTest extends FastSortAlgorithmTest {
32+
33+
@Override public SortAlgorithm getInstance() {
34+
return OddEvenSort.INSTANCE;
35+
}
36+
37+
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /