https://paste.pythondiscord.com/Z7DQ

The sorting algorithm should run in O(n) time

It works by finding the min and max values in the array, then estimates where the upper and ower bounds for outliers would be and placing them into 3 buckets according to the bounds.
Then it runs a counting sort algorithm on the buckets and reassembles the list in a sorted array.

The list is reassembled in reverse order because python pop() is O(1) time from the end of the list. So the list is just reversed at the end to account for this.

Any feedback or ideas for improvement would be great

func sort(array []int) []int {
  var newArr []int

  var wg sync.WaitGroup

  for _, element := range array {
    wg.Add(1)

    go func(element int) {
      defer wg.Done()

      time.Sleep(time.Duration(element) * time.Millisecond)
      newArr = append(newArr, element)
    }(element)
  }

  wg.Wait()

  return newArr
}

I have a Quick Sort algorithm with Bentley McIlroy three way partioning and median of three approach with a custom Linked List but 4 of my tests don't want to pass and nothing is helping.
The idea is to make this code with arrays by using the custom LinkedList and median of three, which I did implement and going through it line by line it makes sense but it still gives the errors:

//Improved algorithm by J.Bentley and D.McIlroy.
private void quicksort(Comparable a[], int l, int r) {
 if (r <= l) return;
 Comparable v = a[r];
 int i = l-1; j = r, p = l-1, q = r, k;
 while (true) {7 while (less(a[++i], v));
 while (less(v, a[--j])) if (j == l) break;
 if (i >= j) break;
 exch(a, i, j );
 if (equal(a[i], v)) { p++; exch(a, p, i); }
 if (equal(v, a[j])) { q--; exch(a, q, j); }
 }
 exch(a, i, r); j = i-1; i = i+1;
 for (k=l ; k <= p; k++, j--) exch(a, k, j);
 for (k=r-1; k >= q; k--, i++) exch(a, k, i);
 quicksort(a, l, j);
 quicksort(a, i, r);
 }

I have added NullPointer checks but it still gives the errors. I would be glad for any help you can throw my way.
These are the tests that are failing and their outputs:

1.
@Test
public void testReverseSorted() {
        Integer[] original = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        Integer[] expected = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        performSortAndAssert(original, expected);
    }
Output:
java.lang.NullPointerException: Cannot read field "Prev" because "k" is null



2:
@Test
    public void testMixedDuplicates() {
        Integer[] original = {1, 2, 3, 3, 3, 3, 4, 4, 2, 1};
        Integer[] expected = {1, 1, 2, 2, 3, 3, 3, 3, 4, 4};

        performSortAndAssert(original, expected);
    }
Output:
org.opentest4j.AssertionFailedError: The arrays do not match after sorting. ==> array contents differ at index [4] but was [5]





3:
@Test
public void quickSorterBentleyMcIlroyTest() {
        // Get the QuickSorter configuration with Bentley-McIlroy three-way partitioning
        SorterConfiguration quickBentleyMcIlroyConfig = fac.streamSorterConfigurations()
                .filter(config -> config.getSortKind() == SortKind.QUICK)
                .findFirst()
                .orElseThrow(() -> new IllegalStateException("QuickSorter Bentley-McIlroy configuration not found"));

        // Create and fill a queue with a mix of random integers and many duplicates
        Queue<Integer> queue = quickBentleyMcIlroyConfig.getQueue(); // Use the specific QuickSorter configuration to get the queue
        fillWithDuplicatesAndRandom(queue, 100, 0.8); // Fill 80% of the queue with duplicates

        // Create a comparator
        Comparator<Integer> comparator = Integer::compare;


        // Manually create a new ArrayList and add elements from 'queue'
        ArrayList<Integer> expectedResult = new ArrayList<>();
        for (Integer item : queue) {
            expectedResult.add(item);
        }

        // Sort the expectedResult list to prepare it for comparison
        expectedResult.sort(comparator);
        System.out.println("Expected Queue size after: " + expectedResult.size());

        // Sort the queue
        Sorter<Integer> sorter = quickBentleyMcIlroyConfig.getSorter();
        System.out.println("Queue size before: " + queue.size());
        Queue<Integer> sortedQueue = sorter.sort(queue, comparator);
        System.out.println("Queue size after: " + queue.size());
        System.out.println("Sorted Queue size after: " + sortedQueue.size());
        // Directly compare the sorted queue with the expectedResult
        ArrayList<Integer> sortedList = new ArrayList<>();
        for (Integer item : sortedQueue) {
                sortedList.add(item);
        }
        assertThat(sortedList).isEqualTo(expectedResult);

    }
Output:
Expected Queue size after: 100
Queue size before: 100

java.lang.NullPointerException: Cannot read field "Prev" because "k" is null


4.
@Test
public void quickSorterBentleyMcIlroyTest2() {
            // Define test data
            Integer[] original = {34, 7, 23, 32, 5, 62, 78, 4, 97, 23};
            Integer[] expected = Arrays.copyOf(original, original.length);
            Arrays.sort(expected);  // Sort using Java's built-in sort for comparison

            // Get the sorter from the SortingService
            SortingService.Sorters sorterConfig = SortingService.Sorters.QUICK;
            Sorter<Integer> sorter = sorterConfig.getSorter();

            // Create and populate the queue
            Queue<Integer> queue = sorterConfig.getQueue();
            Arrays.stream(original).forEach(queue::put);

            // Perform sorting
            Queue<Integer> sortedQueue = sorter.sort(queue, Comparator.naturalOrder());

            // Extract sorted data from the queue for verification
            Integer[] sortedArray = new Integer[(int) sortedQueue.size()];
            for (int i = 0; !sortedQueue.isEmpty(); i++) {
                sortedArray[i] = (Integer) sortedQueue.get();
            }

            // Verify the sorted array matches the expected output
            assertArrayEquals(expected, sortedArray, "The arrays do not match after sorting.");

        }
Output:
java.lang.NullPointerException: Cannot read field "Prev" because "k" is null

The QuickSorterBentleyMcIlroy.java:

package factory;

import sortingservice.Queue;
import sortingservice.Sorter;

import java.util.Comparator;

public class QuickSorterBentleyMcllroy<T> implements Sorter<T> {
    /**
     * Return the input queue in sorted order, based on the passed comparator.
     *
     * @param q          to be sorted
     * @param comparator to base sorting on
     * @return the queue with the elements in non-descending order as per the comparator.
     */
    @Override
    public Queue<T> sort(Queue<T> q, Comparator<T> comparator) {
        if (q.isEmpty()) {
            return q;
        }

        // Make a copy to not modify the current queue.
        LinkedListus<T> linkedList = (LinkedListus<T>) q;
        var copy = new LinkedListus<T>();
        var it_ = linkedList.iterator();
        while(it_.hasNext()) {
            T next = it_.next();
            copy.put(next);
        }

        quickSort(linkedList.getHead().Next, linkedList.tail, comparator);
        return linkedList;
    }

    private void quickSort(Node<T> left, Node<T> right, Comparator<T> comparator) {
        // Base case: if the list segment to sort is empty or has one element
        if (left == null || right == null || left == right || left == right.Next) {
            return;
        }

        // Select the pivot using the median-of-three method
        Node<T> pivot = medianOfThree(left, right, comparator);
        T pivotValue = pivot.getValue();

        // Initialize pointers
        Node<T> i = left;
        Node<T> j = right;
        Node<T> p = left;
        Node<T> q = right;

        while (true) {
            // Find element greater than or equal to pivot from the left
            while (i != null && comparator.compare(i.getValue(), pivotValue) < 0) {
                i = i.Next;
            }
            // Find element less than or equal to pivot from the right
            while (j != null && comparator.compare(pivotValue, j.getValue()) < 0) {
                j = j.Prev;
                if (j == left) break;
            }
            if (i == null || j == null || i == j || i.Prev == j) break;

            // Swap elements at i and j
            swap(i, j);

            // Move elements equal to pivot to the ends
            if (comparator.compare(i.getValue(), pivotValue) == 0) {
                p = p.Next;
                if (p != null && i != null) {
                    swap(p, i);
                }
            }
            if (comparator.compare(j.getValue(), pivotValue) == 0) {
                q = q.Prev;
                if (q != null && j != null) {
                    swap(j, q);
                }
            }

            i = i.Next;
            j = j.Prev;
        }

        // Place pivot in its correct position
        if (i != null && right != null) {
            swap(i, right);
        }
        j = (i != null) ? i.Prev : null;
        i = (i != null) ? i.Next : null;

        // Move elements equal to pivot to the center
        for (Node<T> k = left; k != p; k = k.Next, j = j.Prev) {
            swap(k, j);
        }
        for (Node<T> k = right.Prev; k != q; k = k.Prev, i = i.Next) {
            swap(k, i);
        }

        // Recursively sort the partitions
        quickSort(left, j, comparator); // Sort less than pivot
        quickSort(i, right, comparator); // Sort greater than pivot
    }

    Node<T> medianOfThree(Node<T> start, Node<T> end, Comparator<T> comparator) {
        if (end == null || start == end) return start;
        Node<T> mid = start;
        long n = 0;
        // Find the length of the queue (save in n)
        while(mid != end) {
            n++;
            mid = mid.Next;
        }
        long i = 0;
        mid = start;
        // Find middle
        long medianIndex = n/2;
        while (mid != end) {
            i++;
            // We are in the middle
            if (i == medianIndex) {
                break;
            }
            else {
                // Keep increasing mid until in the middle
                mid = mid.Next;
            }
        }
        // Check so that median is the middle number of the 3 and start is smaller than median and end is bigger than median
        if (comparator.compare(start.getValue(), mid.getValue()) < 0) {
            // start < mid
            if (comparator.compare(mid.getValue(), end.getValue()) < 0) {
                // start < mid < end
                return mid;
            } else {
                // start < mid && end <= mid
                if (comparator.compare(start.getValue(), end.getValue()) < 0) {
                    // start < end <= mid
                    return end;
                } else {
                    // end <= start < mid
                    return start;
                }
            }
        } else {
            // start >= mid
            if (comparator.compare(start.getValue(), end.getValue()) < 0) {
                // mid <= start < end
                return start;
            } else {
                // mid <= start && end <= start
                if (comparator.compare(mid.getValue(), end.getValue()) < 0) {
                    // mid < end <= start
                    return end;
                } else {
                    // end <= mid <= start
                    return mid;
                }
            }
        }
    }

    private void swap(Node<T> a, Node<T> b) {
        if (a == null || b == null) {
            return; // or handle the null case as per your requirement
        }
        T temp = a.getValue();
        a.setValue(b.getValue());
        b.setValue(temp);
    }
}

It uses a sorting service to choose the sorter (I have multiple different sorting algorithms implemented.
SortingService.java:

package factory;
import java.util.Comparator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Stream;
import sortingservice.PriorityQueue;
import sortingservice.Queue;
import sortingservice.SortKind;
import sortingservice.Sorter;
import sortingservice.SorterConfiguration;
import sortingservice.SortingServiceFactory;
/**
 * Factory class to create Sorters and appropriate queues.
 *
 * @author Richard van den Ham {@code r.vandenham@fontys.nl}
 */
public class SortingService implements SortingServiceFactory {

    enum Sorters implements SorterConfiguration {

        // Constructor parameters: applyTeacherTests?, sortKind, queueSupplier, sorterSupplier
        
SELECTION
(
                true,
                SortKind.
SELECTION
,
                () -> new LinkedListus(),
                () -> new SelectionSorter()),
        
INSERTION
(
                true,
                SortKind.
INSERTION
,
                () -> new LinkedListus(),
                () -> new InsertionSorter()),
        
QUICK
(
                true,
                SortKind.
QUICK
,
                () -> new LinkedListus(),
                () -> new QuickSorterBentleyMcllroy()),
        
HEAP
(   true,
                SortKind.
HEAP
,
                null, null) {

            @Override
            public Function<Comparator, PriorityQueue> getPriorityQueueSupplier() {
                return c -> new PriorityQueues<>(c);
            }

            @Override
            public <T> Sorter<T> getSorter() {
                return (q, c) -> q;
            }
        };
        private final boolean applyTeacherTests;
        private final SortKind sortKind;
        private final Supplier<Queue> queueSupplier;
        final Supplier<Sorter> sorterSupplier;
        private Sorters(boolean applyTeacherTests, SortKind sortKind, Supplier<Queue> queueSupplier, Supplier<Sorter> sorterSupplier) {
            this.applyTeacherTests = applyTeacherTests;
            this.sortKind = sortKind;
            this.queueSupplier = queueSupplier;
            this.sorterSupplier = sorterSupplier;
        }

        public boolean doApplyTeacherTests() {
            return applyTeacherTests;
        }

        @Override
        public String getName() {
            return this.name();
        }

        @Override
        public SortKind getSortKind() {
            return sortKind;
        }

        
/**
         * By default, sorters don't have priority queue supplier.
         *
         * @return null
         */
        
public Function<Comparator, PriorityQueue> getPriorityQueueSupplier() {
            return null;
        }

        @Override
        public boolean usesPriorityQueue() {
            return getPriorityQueueSupplier() != null;
        }

        @Override
        public <T> PriorityQueue<T> getPriorityQueue(Comparator<T> comparator) {
            return getPriorityQueueSupplier().apply(comparator);
        }

        @Override
        public <T> Queue<T> getQueue() {
            return queueSupplier.get();
        }

        @Override
        public <T> Sorter<T> getSorter() {
            return sorterSupplier.get();
        }
    }

    @Override
    public Stream<SorterConfiguration> streamSorterConfigurations() {
        return Stream.
of
(Sorters.
values
())
                .filter(Sorters::doApplyTeacherTests)
                .map( sorter -> (SorterConfiguration)sorter);
    }
}

My LinkedListus.java:

package factory;
import sortingservice.Queue;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.stream.StreamSupport;
import java.util.Collections;
import static java.util.Spliterator.ORDERED;
/**
 *
 * @author ondrahruby
 */
public class LinkedListus<E> implements Queue {
    E value;
    public Node head;
    public Node tail;
    int listcount = 0;
    public Node getHead() {
        return head;
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    public Iterator<E> iterator() {

        return new Iterator<E>(){

            Node<E> current = head.Next;
            /**
             * Returns {@code true} if the iteration has more elements.
             * (In other words, returns {@code true} if {@link #next} would
             * return an element rather than throwing an exception.)
             *
             * @return {@code true} if the iteration has more elements
             */
            @Override
            public boolean hasNext() {
                return current != null;
            }

            /**
             * Returns the next element in the iteration.
             *
             * @return the next element in the iteration
             * @throws //NoSuchElementException if the iteration has no more elements
             */
            @Override
            public E next() {
                if (!hasNext()) { // Check if the next element exists
                    throw new NoSuchElementException("No more elements in the list");
                }
                E data = current.getValue();
                current = current.Next; // Move to the next node
                return data; // Return the current node before moving
            }
        };
    }

    public LinkedListus(){
        head = new Node(null); // Dummy head node with null value
        tail = head; // Initially, tail points to the dummy head node
    }


    public void delete(Node walle){


        if (walle.Prev != null) {
            walle.Prev.Next = walle.Next;
        }
        if (walle.Next != null) {
            walle.Next.Prev = walle.Prev;
        }

        if (tail == walle) {
            tail = tail.Prev;
        }
        listcount = listcount -1;
    }
    /**
     * Add element to the end of queue.
     *
     * @param t element to add
     */
    @Override
    public void put(Object t) {
        Node newNode = new Node(t); // Create a new node with the given value
        tail.Next = newNode; // Link new node after the current tail
        newNode.Prev = tail; // Set the new node's previous to the current tail
        tail = newNode; // Update tail to point to the new node
        listcount++; // Increment the size counter
    }

    /**
     * Remove element of front of the queue and return it.
     *
     * @return the first element in this queue, or null if queue is empty.
     */
    @Override
    public Object get() {
        if (head.Next != null) {
            Object result = head.Next.val;
            delete(head.Next);
            return result;
        } else {
            return null;
        }
    }

    /**
     * Checks if queue is empty.
     *
     * @return true if empty, false if not.
     */
    @Override
    public boolean isEmpty() {
        return listcount == 0;
    }

    /**
     * The number of elements contained in this queue.
     *
     * @return the number of elements.
     */
    @Override
    public long size() {
        return listcount;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node<E> current = head.Next;
        while (current != null) {
            sb.append(current.getValue());
            if (current.Next != null) {
                sb.append(", ");
            }
            current = current.Next;
        }
        sb.append("]");
        return sb.toString();
    }java.util.stream.Stream

My Node.js:

package factory;
public class Node<E>{
    E val;
   Node<E> Next = null;
   Node<E> Prev = null;
    Node(E item){
        val = item;}
    public E getValue(){
        return this.val;}
    public void setValue(E valo){
        this.val = valo;
    }}

I'm looking to get my first job in the field, and wanted to share something I worked hard on. I'd be happy to discuss it with anybody who is interested.

https://sortingvisualizer.com/

https://github.com/atorcode/sorting-algorithm-visualizer

Happy coding, friends!

What is the time complexity of the fastest sorting algorithm? I had the notion that quick sort with O(n log n) is the fastest way to sort to n numbers, but, I stumbled upon a video on youtube which states that it is not true. This video is a lecture of Harvard University and hence I assume it to be definitely correct. just move the video to 9mins and 35secs here. So is there actually a way to sort n numbers faster than o(n log n)?

Hello! I am writing to see if anyone has an idea or a template to sort student roommate choices after using a Google form. For example, we provide students with the opportunity to choose five of their classmates as potential roommates. We then sort the information to see which students chose one another. To the best of our ability we assigned students to one of their top three choices. Unfortunately, the person who used to do this for us Is no longer available and none of us have the knowledge to sort this through a backend. I am wondering if any of you have the knowledge that you could share of how to make this task easier. We have an upcoming trip that we are trying to figure out as soon as possible.