Tag: Sorting

Kotlin Koans—Part 18

This portion of the Kotlin Koans tutorial deals with sorting a collection functionally. As usual with Kotlin, this wasn’t a very difficult problem. As a matter of fact, it’s only one line of code.

fun Shop.getCustomersSortedByNumberOfOrders(): List {
    return customers.sortedBy { it.orders.size }
}

We basically just call the sortedBy method and place the property we want to sort by inside of the curly braces { }. In this case, I wanted to sort by the number of orders my hypothetical customer placed, so I used it.orders.size.

Just for kicks, I decided to try this in Java 8 to see the difference.

public static List getCustomersSortedByNumberOfOrders(Shop shop){
    return shop.getCustomers()
            .stream()
            .sorted(Comparator.comparingInt(customer -> customer.getOrders().size()))
            .collect(Collectors.toList());
}

Once again, we can do the same thing in Java that we can do in Kotlin at the expense of more verbosity. Also, I think in this case, the Java approach is more difficult to learn and more prone to errors since we are chaining a bunch of functions together to achieve the same result that we can do in one line of Kotlin code.

You can click here to see Part 17

Advertisement

Kotlin Koan—Part 13

Kotlin has nice extensions on Collection classes. JDK has provided developers a way to sort collections for a long time now, but often times, it’s done with external classes such as Collections. This puts us in a odd position of using procedural programming when performing operations such as sorting a collection.

A more OOP approach would be to have a sort method directly on a Collection as opposed to passing a collection to an external class with a static method. Kotlin extends Java collections by using its extension feature to complement the collection classes found in JDK.

Here is an example that demonstrates how to sort an ArrayList in Java.

fun task12(): List {
    val lst =  arrayListOf(1, 5, 2)
    lst.sortDescending()
    return lst
}

If all fairness to Java, JDK 8 did address this issue. Here is the equivalent Java code that does the same thing.

public class CollectionSort {
    public List sortList(){
        List lst = Arrays.asList(1, 5, 2);
        lst.sort(Comparator.reverseOrder());
        return lst;
    }
}

I’m not going to complain too much about the Java 8 syntax, but I think sortDescending() and sortAcending() is more readable than Comparator.natualOrder() and Comparator.reverseOrder(). However, the Kotlin approach is much superior to JDK 7 and earlier.

You can read the previous post here.

Kotlin Koans—Part 11

This portion of the Kotlin Koans tutorial focuses on Object Expressions. Practically speaking, Object Expressions serve the same role as anonymous innner classes in Java. They let us make modifications on a class in one particular case without having to create an entirely new class.

This portion of the tutorial has developers creating a dynamic Comparator class that sorts numbers in descending order.

fun task10(): List {
    val arrayList = arrayListOf(1, 5, 2)
    Collections.sort(arrayList, object: Comparator {
        override fun compare(o1: Int?, o2: Int?): Int {
            return o2?.compareTo(o1 ?: 0) ?: 0
        }
    })
    return arrayList
}

We could have used a lambda in this case, but that would miss the point of what the tutorial is trying to teach. In this code snippet, the second paramter of Collections.sort is an Object Expression that defines a custom Comparator class.

You’ll notice that the definition of compare is full of null safe expressions as indicated the by ? and ?: opeartors. As a side note, I really like how Kotlin has an arrayListOf() function that let’s you create an ArrayList. Sure it does the same thing as Arrays.asList, but again, it’s more concise.

You can view part 10 here

Insertion Sort—Python

Insertion sorts are a common sorting technique that many computer science students are asked to learn. Here is a Python implementation of an Insertion Sort.

def insertion_sort(items):
    for i in range(2, len(items) - 1):
        item = items[i]
        j = i
        while (items[j - 1] > item) and (j >= 1):
            items[j] = items[j - 1]
            j -= 1
        items[j] = item

if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    insertion_sort(items)
    print(items)

Insertion sorts use nested loops and test if an item at the end of the list is less than an item in the front of the list. If they are, the code does a swap.

When run, we get this output:

['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Tina Belcher', 'Louise Belcher']

Quick Sort—Python

Quick sort is a sorting algorithm that uses recursion and nested loops to sort items. Here is an implementation in Python

def split_list(unsorted, low, high):
    # Set our temp item at the low end
    item = unsorted[low]

    # Variables for tracking left and right
    # side of the list
    left = low
    right = high

    # loop until our left side is less than right side
    while left < right:

        # Move left to the right while it's less than item
        while unsorted[left] <= item and left  item:
            right -= 1

        # Check if we need to swap elements
        if left  low:
        # Split unsorted into two lists
        index = split_list(unsorted, low, high)

        # Sort the left hand of the list using recursion
        quick_sort(unsorted, low, index - 1)

        # Sort the right hand of the list using recursion
        quick_sort(unsorted, index + 1, high)


if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    quick_sort(items, 0, len(items) - 1)
    print(items)

When run, this code will produce the following output

['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Louise Belcher', 'Tina Belcher']

The key in this algorithm is that we split our list into two halfs and then use recursion to sort each half. The work of swapping elements takes place in the split_list function. However, the quick_sort function is responsible for calling split_list until all items are sorted.

Selection Sort—Python

Selection sorts are a very common method of sorting. Here is a selection sort that is implemented in Python.

def selection_sort(items):
    for i in range(len(items) - 1):
        # Assume that the smallest item is located at index i
        smallest = i

        # Now loop through the rest of the list
        for j in range(i + 1, len(items)):
            # Is our item at index j smaller than our smallest item?
            if items[j] < items[smallest]:
                smallest = j

        #  Now swap elements to perform the sort
        temp = items[smallest]
        items[smallest] = items[i]
        items[i] = temp

if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Gene Belcher', 'Tina Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    selection_sort(items)
    print(items)

Selection sorts use nested loops to iterate over a list. We check if the item at index j is less than the current smallest item. If j is smaller than smaller, we assign smaller to j.

Once we complete the nested loop, we can perform a swap. Our driver program demonstrates this with strings, but thanks to Python's duck typing system, this will sort any object that implements __lt__.

When run, we get this output

['Bob Belcher', 'Linda Belcher', 'Gene Belcher', 'Tina Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Louise Belcher', 'Tina Belcher']

Bubble Sort—Java

The bubble sort is a very common algorithm that many computer science students are expected to learn. Yesterday I did a post that shows a Python implementation of the bubble sort which you can view here. Today I will demonstrate the same technique in Java.

import java.util.Arrays;

public class BubbleSort {

public static void main(String [] args){
Integer [] nums = {9, 4, 2, 1, 10};
System.out.println("Unsorted is " + Arrays.toString(nums));

bubbleSort(nums);
System.out.println("Sorted is " + Arrays.toString(nums));
}

public static<T extends Comparable> void bubbleSort(T [] array){
int n = array.length;
T temp;

for(int i = 0; i < n; i++){
for (int j = 1; j  0){
//Swap the elements
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
}

Java is a little more verbose than Python. Since it is a statically typed language (which means you have to declare the data type up front, as opposed to Python’s duck typing method), I chose to use generics to implement this sort.

Generics were introduced in JDK 1.5. They allow us to write code that is widely applicable to many types of objects without forcing us to use the Object class. You can find a wide use of generics in the java.util package.

In this case, I declared my generic method like this

public static<T extends Comparable> void bubbleSort(T [] array){

Let’s go through this one word at a time.

  1. public—This is the keyword that makes this method publically available
  2. static—This keyword attaches this method to the class rather than an object
  3. <T extends Comparable>—This is the code that declares this method to be a generic method. T is the type of the object, followed by extends Comparable which means that any object that implements the Comparable interface is accetable to this method.
  4. T [] array—This declares an array of type T (which is any class that implements Comparable in this case)

Now that we have declared this to be a generic method, this method will work with any object that implements the Comparable interface. The Comparable interface is widely used throughout Java in sorting. It declares a compareTo(T obj) method which returns a positive number when an item is greater than the comparing object, zero when the two objects are equal, and a negative number when the comparing object is less than the other object.

Since this interface exists, Java lets us sort anything that implements this interface easily. That allows programmers a high degree of freedom and flexibility when creating custom classes because the programmer gets to decide how one object is greater than, less than, or equal to another object.

We apply the Comparable interface to this bubble sort method here

if(array[j - 1].compareTo(array[j]) > 0){
//Swap the elements
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}

If the left hand portion array[j - 1].compareTo(array[j]) is 0, then these two items are 0. If the result is a negative number then array[j - 1] is less than array[j], otherwise array[j - 1] is greater than array[j] and it needs to get swapped.

When run, we get this output

Unsorted is [9, 4, 2, 1, 10]
Sorted is [1, 2, 4, 9, 10]

Bubble Sort—Python

Many computer science students are expected to perform sorting. Here is an example of doing a bubble sort in Python.

def bubble_sort(array):
    # Grab the length of the array
    n = len(array)

    # Iterate through array from 0 to n
    for i in range(len(array)):

        # Iterate through array from 1 to n - i
        for j in range(1, n - i):

            # Now check if the element at array[j - 1] is larger than array[j]
            if array[j - 1] > array[j]:
                # Perform a swap of the elements
                temp = array[j - 1]
                array[j - 1] = array[j]
                array[j] = temp

if __name__ == '__main__':
    unsorted = [10, 5, 2, 3, 1]
    print('Unsorted list is: ', unsorted)

    bubble_sort(unsorted)
    print('Sorted list is now: ', unsorted)
%d bloggers like this: