Data Structures - Stacks and Queues

In this post we'll go over some things about stacks and queues.
I have in an earlier post wrote an implementation of a queue while explaining lists. You can take a look here.

Queues:
Queues are FIFO, meaning first in first out. The first element put into the queue is dequeued in the before the others. There is a head and a tail that keeps track of the first and last element enqueued.

Priority queues:
Priority queues are used in storing processes and their priorities. When a system has to switch the processor between many many processes going on, it can switch based on priorities. Some processes have lower priority and some, higher.

Circular Queues:
Circular queues are the same as queues, except that it wraps around the end to the beginning again. With circular queues, it would be easy to use an array, since there is only a limited amount of space in a circle.

Stacks:
Stacks are FILO, meaning first in last out. Think of the stack like, a stack of plates. If you stack one plate over another, say five plates, you would take each one off one by one from the fifth one you stacked to the first one at the very bottom. Stacks are used for memory storage in systems, can be allocated for a process.

These two data structures, as you can see my examples of them, are used in important systems and programs.

Read More

Sorting Algorithms - Insertion Sort

Pic from Geeksquiz

Insertion Sort is utilized to sort a group of elements from smallest to largest. Here's how it works:

Lets say we start with an array A = {15, 16, 12, 7, 9}. This array is not sorted(least to greatest).

Pseudocode:

Insertion-Sort(A)

1.    for j = 2 to A.length do

2.        key = A[j]

3.        i = j - 1

4.        while i > 0 and A[i] > key do

5.            A[i+1] = A[i]

6.            i = i - 1

7.        A[i + 1] = key

Walk-through:

Starting with the unsorted array {15, 16, 12, 7, 9}...

line #1: j is 2. array is unchanged {15, 16, 12, 7, 9}

line #2: key is 16

line #3: i is 1

line#4: loops while i is not going out of bounds and A[i] is bigger than the key(current j that we are comparing)

line#7: we skipped lines 5 and 6 because A[i](15) was not bigger than key(16). We basically copy the key back into i + 1 in which this case it is also j.

line#1: j = 3 array is {15, 16, 12, 7, 9}

line#2: key is 12

line#3: i is 2

line#4: loops while i is not going out of bounds and A[i] is bigger than the key(current j that we are   comparing)

line#5: 16 > 12, so A[i + 1] = A[i] OR {15, 16, 16, 7, 9}

line#6: i is 1

line#7: A[i + 1] = key OR {15, 12, 16, 7, 9}

line#5: 15 > 12, so A[i + 1] = A[i] OR  {15, 15, 16, 7, 9}

line#6: i is 0

line#7: A[i+1]  = key OR {12, 15, 16, 7, 9}

See here that first three elements are now already sorted, if we keep going with the pseudocode we will eventually come to the sorted {7, 9, 12, 15, 16}. Try doing the rest!

Analysis: 

Worst Case: The worse array that can go through this is some array that is sorted in reverse order e.g, {19, 15, 13, 7, 3, 1} 

In this case, the algorithm will have to go through and compare each number to more and more numbers.

For example, the worst case array presented here will first compare 15 once, then compare 13 twice, then 7 three times, 3 four times, and 1 five times:

                                                     1 + 2 + 3 + 4 + 5........

In terms of the length of the array n, it will compare a total of:
                                                            n(n + 1)/ 2  OR  (n^2 + n)/2 times

As you accumulate more knowledge or already have, you will see that O(n^2) is not very nice a time compared to some others.

Read More

Data Structures - Arrays and Linked Lists

An array is a random access data structure, while a linked list is a sequential access data structure. So, what's the difference between random and sequential?

Well, random means you can access something directly, and sequential means in order to access something, you have to go one by one. See this:

Arrays:

Linked lists:

or

The differences between the two different linked lists, we'll talk about later. But the difference between arrays and linked lists, we will talk about :D

Okay, the difference: Arrays, can be access directly, like some array A and some index -> A[0].

In the above example of an array, A[0] would = 10, A[1] = 6,  A[2] = 7, and so on. The way to access these indices is very direct, like opening a book to a specific page, assuming that there's bookmarks to every page...

Linked lists on the other hand, are linked someway, the first one in only one direction. For the first linked list, it is analogous to......to.......... walking into a huge cave and every step you get a boulder behind you, you can't go back, sadly.

The second one is linked bidirectionally, which means you can go back and forth between elements, like a string of rooms each with a door. 

Yup, that's all.

I'll add more to this if I find that I have left anything out, and I hope this explains to you arrays and linked lists!

Here's to part 2: Implementation

Read More