#sortingalgorithms

[sirtbhopal]

Seminar on Sorting Out the Future - SIRT Bhopal

Join us for an insightful seminar on “Sorting in Data Structures” with expert “Mr. Pradeep Mishra”, Tech Lead, Virtusa!

Organized by the Department of AIML and CSECS, this session promises to dive deep into the world of data structures and algorithms.

Date: 10th September, 2025 Time: 9:30 - 12:00 PM

Don’t miss this opportunity to learn from the best!

[full-stack-development21]

Master the art of data arrangement with our Sorting in Java module! From quicksort to mergesort, explore various sorting algorithms in Java. Optimize your code and gain the skills to efficiently organize data sets. Join us to become a Java sorting maestro!

[kazexmoug-blog]

When your average case is also your worst case and you actually know what it means.......THANKS ARRAYS LOL!!!!!! #coding #datastructuresandalgorithms #learningtocode #computerscience #sortingalgorithms #timecomplexity #bubblesort #insertionsort #selectionsort #bigotime #computerscienceisfun #learningsomethingnew #learningtoimprove #selftaughtcoder #kazexmoug #learningtech #timecomplexity #spacecomplexity #runtimes #algorithms #softawareengineering #mathisfun #computerscienceforeveryone #codingmakesmehappy #mathisnotscary #teachyourselfcode #algorithmanalysis #gettingoutofmyhead #criticalthinking #entryleveltech https://www.instagram.com/p/Bz3ONFXpZYe/?igshid=ibaa3jipzdz

[kiasalehi]

Quicksort

Quicksort is a very elegant nlogn sorting algorithm. It involves recursively partitioning the array on either side of a “pivot” element such that all elements before the pivot are smaller than the pivot, and all elements after the pivot are larger than the pivot. Doing this repeatedly on each partition sorts the array.

1. Choose a pivot. For starters let’s just choose the last element in the array.

2. Partition the array so that smaller-than-pivot elements are to the left of the pivot, and larger elements are to the right.

Starting at the left, we will have 2 counters, one to tell us the index of the last swap, i, and one for the current index, j. Both are initialized to 0. 

We will now traverse the array by incrementing j. If the element at j is larger than the pivot, skip it -- this will cause it to fall into the right side partition by default. Increment j. 

If arr[j] is smaller than the pivot, that’s one we want in the left partition! How do we get it there? We will swap it with the element at i, which indicates the index of the last swap (plus one), and therefore guarantees all elements before it are smaller than the pivot. Once we’ve swapped, we increment i since the index of the last swap has changed, and we continue incrementing j to keep checking the remaining elements.

Once j reaches the element before the pivot, we are done with the first partition: elements before i are smaller than the pivot, and elements after i are larger than it. Now we just need to put our pivot in between those, and it will be in its ‘rightful position’ in the final array. To do this, we swap the pivot with the element at i. 

3. Recursively sort the partitions we just created. Remember, the pivot does not need to be included because it is already in the correct place! 

I realized the code I wrote for this is on my other computer, and I’m feeling lazy, so I will add that to this post later.

Here’s the YouTube explanation that I found to be the most helpful: 

[kiasalehi]

Merge sort

Merge sort is a method of sorting an array in O(n*log(n)) time.

Start with an array: [5, 2, 4, 1, 3]

Break it in half (roughly).

Right half: [5, 2, 4]

Left half: [1, 3]

Do it again for each half.

Left half’s right half: [5, 4]

Left half’s left half: [2]

------------------------

Right half’s left half: [1]

Right half’s right half: [3]

Once more for the one that isn’t a single element yet: Break [5, 4] into [5] and [4].

These single-element arrays are sorted already. That’s our base case! Now to output a full array that’s sorted we start recombining the single-element arrays in a specific way. The deepest level of recursion we reached was with [5] and [4] (3 levels deep because we broke in half 3 times before we reached single-element arrays). So we start there when we begin working our way back up. How do we merge [5] and [4] into a sorted array? We read and compare the elements in each array, one by one. In this case the first and only elements in question are 5 and 4. Since 5 is more than 4, we add 4 to our result array: merged = [4]. Then since we’re done with it, we remove it from the array it came from. Now we are comparing the arrays [5] and []. Since one array is completely empty, and the other one is guaranteed to be sorted, we can just tack on the remaining array to our merged array to get: merged = [4, 5]. By the same logic, [1] and [3] recombine one level up into [1, 3]. So far all very trivial.

Now, we move one level up again: how do we combine [4, 5] with [2]? 

As before, we will compare the elements of each array, one by one. Up first: 4 and 2. 2 is smaller, so add 2 to the resulting array for this step: merged = [2]. Also, remove it from the array it came from (that is, from the subproblem of sorting [2], which of course returned [2]). Now we are comparing [4, 5] and []. Again, we have completely finished with one of the arrays, so we tack on all the leftover array to the resulting array: merged = [2, 4, 5].

By similar logic, we can combine the [1] and [3] from the right half of the original array to get [1, 3]. That leaves us with the final step of combining [2, 4, 5] with [1, 3]. Going through the arrays element by element, the first values in question are 2 and 1. 1 is smaller so we add 1 to the result for this step: merged = [1]. (Notice how since we are in a different stack frame for each of these subproblems we start with a fresh value for merged every time.) We remove 1 from its place in [1, 3] so the remaining comparisons will be between [2, 4, 5] and [3]. Up first: 2 vs 3. 2 is smaller so we move it from its current place to the final array: [2, 4, 5] becomes [4, 5] and merged becomes [1, 2]. Comparing [4, 5] and [3], we first check 4 vs 3. 3 is smaller so we move it to the result: merged = [1, 2, 3] and the remaining arrays are [4, 5] and []. As before, when one of the arrays becomes empty, we can safely tack on the remaining array to the result for a fully sorted solution: merged = [1, 2, 3, 4, 5]. Nice job!

Here is an example implementation of the process we just described in Ruby:

[cardboardvoice-blog]

"Sorting Algorihms" - Grumpy Codes 014 Follow me on Tapastic. #sadako #developers #codes #sorting #sortingalgorithms #efficientsort #humor #funny #lol #ghost #developers #programmers #programming #coding #codes #painttoolsai #comic

[exacs-blog]

Ese momento en el que ves la guía del estudiante de AED y ves que se van a estudiar algoritmos de ordenación

Guía del estudiante de Algoritmos y Estructuras de Datos

[exacs-blog]

Algoritmos de Ordenación. Corrección de errores

En este post vamos a terminar con los algoritmos de ordenación. En concreto, contaremos qué vamos a usar para probarlos y luego haremos unas correcciones de algunos de ellos.

Generadores de Array (parte II)

Hemos añadido dos nuevos métodos para generar arrays aleatorios.

Uno se llama almostOrdered que genera un array casi ordenado: consiste en un array de números de 0 a n, en el que solo 1 elemento está intercambiado con el siguiente.

Otro es fewElements que genera un array con muy pocos elementos diferentes pero muy repetidos. Por ejemplo, un array de 100 elementos en el que todos son 0, 1 y 2.

Sobre las pruebas, hay una clase que es TrialIO que tiene un main y se encarga de hacer las pruebas. Podéis modificar el array de prueba en la línea 8 de dicho código.

Correcciones en los algoritmos

Al hacer las pruebas, hemos observado que había algoritmos con errores. Los teníamos en CombSort y en QuickSort.

Aquí tenéis el commit con la modificación hecha en CombSort. Con esto garantizamos que, el bucle no se romperá hasta que haya habido al menos una iteración con gap igual a 1.

Y aquí el commit con la modificación hecha en QuickSort. En lugar de dividir la lista en dos, la dividimos en tres: elementos menores que el pivote, elementos iguales que el pivote y elementos mayores que el pivote.

Y con esto, damos por finalizado #SortingAlgorithms. En este enlace podéis ver todos los posts de este proyecto y aquí tenéis el código completo en su versión más reciente.

Xaoo! (cada vez que leo esta despedida me parece más absurda)