Skip to content

Add LibrarySort Implementation #7481

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
Rosander0 wants to merge 1 commit into
base: master
Choose a base branch
from
+124 −0
Open

Add LibrarySort Implementation #7481

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
79 changes: 79 additions & 0 deletions src/main/java/com/thealgorithms/sorts/LibrarySort.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,79 @@
package com.thealgorithms.sorts;
// author: Vraj Prajapati @Rosander0

/**
* Library Sort (also known as Gapped Insertion Sort) is a sorting algorithm
* that works like insertion sort but leaves gaps between elements to make
* future insertions faster.
* Time Complexity: O(n log n) average case
* Space Complexity: O(n)
*
* @see <a href="https://en.wikipedia.org/wiki/Library_sort">
* Wikipedia: Library Sort</a>
*/
public final class LibrarySort {

private LibrarySort() {
// Utility class
}

/**
* Sorts an array using the Library Sort algorithm.
*
* @param array the array to sort (must not be null)
* @return the sorted array
*/
public static int[] sort(final int[] array) {
if (array == null) {
throw new IllegalArgumentException("Input array must not be null!");
}
if (array.length <= 1) {
return array;
}

int n = array.length;
Integer[] spaced = new Integer[2 * n];

spaced[0] = array[0];
int inserted = 1;

for (int i = 1; i < n; i++) {
int pos = binarySearch(spaced, inserted, array[i]);
for (int j = inserted; j > pos; j--) {
spaced[j] = spaced[j - 1];
}
spaced[pos] = array[i];
inserted++;
}

int idx = 0;
for (int i = 0; i < 2 * n; i++) {
if (spaced[i] != null) {
array[idx++] = spaced[i];
}
}
return array;
}

/**
* Binary search to find insertion position among inserted elements.
*
* @param spaced the spaced array
* @param inserted number of elements inserted so far
* @param target the value to find position for
* @return the correct insertion index
*/
private static int binarySearch(final Integer[] spaced, final int inserted, final int target) {
int lo = 0;
int hi = inserted;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (spaced[mid] <= target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
}
45 changes: 45 additions & 0 deletions src/test/java/com/thealgorithms/sorts/LibrarySortTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,45 @@
package com.thealgorithms.sorts;
// author: Vraj Prajapati @Rosander0

import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.Test;

public class LibrarySortTest {

@Test
public void testBasicSort() {
assertArrayEquals(new int[] {1, 2, 3, 4, 5}, LibrarySort.sort(new int[] {5, 3, 1, 4, 2}));
}

@Test
public void testAlreadySorted() {
assertArrayEquals(new int[] {1, 2, 3, 4, 5}, LibrarySort.sort(new int[] {1, 2, 3, 4, 5}));
}

@Test
public void testReverseSorted() {
assertArrayEquals(new int[] {1, 2, 3, 4, 5}, LibrarySort.sort(new int[] {5, 4, 3, 2, 1}));
}

@Test
public void testDuplicates() {
assertArrayEquals(new int[] {1, 2, 2, 3, 3}, LibrarySort.sort(new int[] {3, 2, 1, 3, 2}));
}

@Test
public void testSingleElement() {
assertArrayEquals(new int[] {1}, LibrarySort.sort(new int[] {1}));
}

@Test
public void testEmptyArray() {
assertArrayEquals(new int[] {}, LibrarySort.sort(new int[] {}));
}

@Test
public void testNullArray() {
assertThrows(IllegalArgumentException.class, () -> LibrarySort.sort(null));
}
}
Loading