Selection Sorting Algorithm

Selection Sorting Algorithm

Selection sorting is a fundamental concept in the field of programming that involves recursive algorithms that can sort out a list of properties by its values. 

As you can see, the algorithm will compare the value of the element from the first to the last in the list with the rest of the elements. Eventually, resulting in a sorted list from smallest to largest

When the algorithm is running it starts off at the first element and go down the list of other elements to find the smallest one.

If the list contains a value that is smaller than the pointed value, it will do a swap.

Else the pointer will just move on to the next element in the list.

Let' code it up!

First , we have to ensure we actually have the window to show these rectangles. I am going to use pygames as it is a integrated environment that is easy to use. 

				
					import pygame, random

pygame.init()

# WINDOW
WINDOW_SIZE = 600
WINDOW = pygame.display.set_mode((WINDOW_SIZE, WINDOW_SIZE))
pygame.display.set_caption('Sorting Algorithm Visualization')

Next, we must use some property of the element that is obviously different. The height of rectangles will be a good start, which will be set to random from 20 – 500.

				
					def create_rectangles():
    num_rectangles = WINDOW_SIZE // Rect_width - 5
    rectangles = []
    heights = []

    for i in range(5, num_rectangles ):
            height = random. randint( 20, 500)
            while height in heights:
                height = random.randint(20, 500)

            heights.append(height)
            rect =  Rectangle(BLACK, i * Rect_width, height)
            rectangles.append(rect)

    return rectangles
				
			
				
					GREEN = (0, 255, 0)
BLUE = (0, 0, 255)
BLACK = (0, 0, 0)
PURPLE = (128, 0, 128)
GREY = (154, 166, 178)
LIGHT_BLUE = (64, 224, 208)
WHITE = (248, 250, 252)
SKY_BLUE = (217, 234, 253)

Colours

White -> Unsorted

Purple -> Selected 

Black -> sorted

				
					class Rectangle:
    def __init__ (self, color, x, height):
        self.color = color
        self.x = x
        self.width = Rect_width
        self.height = height

    def select(self):
         self.color = BLACK

    def unselect(self):
        self.color = WHITE

    def set_smallest(self):
        self.color = PURPLE

    def set_sorted(self):
        self.color = BLACK

Alright, now that we have built our variables that we want to sort. We have to build the selection sort algorithm. 

Remember it works by taking the lowest height of the rectangle in the list and compare that with the height of the rectangle it selects.

				
					    def selection_sort(rectangles):
    num_rectangles = len(rectangles)

#set first element as an anchor
    for i in range(num_rectangles):
        min_index = i
        rectangles[i].set_smallest()
        #let j be the elements following in
        for j in range(i + 1 , num_rectangles):
            rectangles[j].select()
            draw_rects(rectangles)
            #then compare the height of j and i to see which on is smaller
            if rectangles[j].height 
				
			
				
					            if rectangles[j].height

This means if height of the original rectangle is smaller than the previously selected rectangle, go ahead and unselect the original rectangle  and select the new rectangle with shortest height. This algorithm let the computer find the shortest height rectangle in the rest of the list from the anchor element.

Now we do the swapping ! 😀

				
					#rectangles[i].x is our anchor then rectangles[min_index].x is the shortest height rectangle we found using our algorithm(selected rectangle)

rectangles[i].x, rectangles[min_index].x = rectangles[min_index].x, rectangles[i].x
        rectangles[i], rectangles[min_index] = rectangles[min_index], rectangles[i]

        rectangles[min_index].unselect()
        rectangles[i].set_sorted()

        draw_rects(rectangles)

We are almost done!

All we have to do now is to do the necessary setting for our pygame to understand the algorithm we are running.

				
					def main():
    rectangles = create_rectangles()
    draw_rects(rectangles)
    sorting_generator = selection_sort(rectangles)

    run =  True
    sorting = False
    while run:
        clock.tick(FPS)
        draw_rects(rectangles)

        if sorting:
            try:
                next(sorting_generator)
            except StopIteration:
                sorting = False
        else:
            draw_rects(rectangles)

        for event in pygame.event.get():

            if event.type == pygame.QUIT:
                run = False

            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_SPACE:
                    sorting = not sorting
                if event.key == pygame.K_q:
                    run = False

        pygame.display.update()

    pygame.quit()
main()

Conclusion

Thank you for reading, this is a very introductory version of algorithms. Even though this is a silly little project, I had tones of fun making this. 

This project is inspired by looking at some youtube video online.

Source code on github