# Elementary Sorts

## Selection Sort

O(1/2(n^2)) -> O(n^2). It is in-place sort. We find smallest value and move it to the front. It is not stable algorithm.

```
class SortArray {

    static void main(String[] args) {
        int[] array = [1, 5, 7, 3, 9, 1, -2]
        println array
        sort(array)
        println array
    }

    static void sort(int[] array) {
        int min
        int temp
        for (int i = 0; i < array.length; i++) {
            min = i
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j
                }
            }
            temp = array[i]
            array[i] = array[min];
            array[min] = temp;
        }
    }
}
```

## Insertion Sort

Complexity is about O(1/4(n^2)) in optimistic case - when the array is partially sorted, this algorithm works perfectly In worst case, it is O(1/2(n^2)) - when the values in reversed order. In general, O(n^2). It is in-place and stable. For sorted list, the complexity is O(n).

```
class InsertionSortArray {

    static void main(String[] args) {
        int[] array = [1, 5, 7, 3, 9, 1, -2]
        println array
        sort(array)
        println array
    }

    static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j -1]) {
                    int temp = array[j]
                    array[j] = array[j - 1]
                    array[j - 1] = temp;
                } else {
                    break
                }
            }
        }
    }
}
```

## Shell Sort

O(n^(3/2). Not stable, can be done in-place.

```
class ShellSortArray {

    static void main(String[] args) {
        int[] array = [1, 5, 7, 3, 9, 1, -2]
        println array
        sort(array)
        println array
    }

    static void sort(int[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, ...

        while (h >= 1) {  // h-sort the array.
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
                    int temp = a[j]
                    a[j] = a[j - h];
                    a[j - h] = temp;

                }
            }
            h = h / 3;
        }
    }
}
```

## Example: shuffle cards randomly

First idea: Generate random numbers and assign them to cards. Then sort the array.

Knuth shuffle: iterate through the cards and generate random number that is between 0 and **i** (**i** is current index).

## Convex Hull

The first approach to calculate a convex hull could be:

1. Find most left point
2. Then find most right point to that point and repeat this until we get to the most left point

```
```

![](/files/-M3xR2zaR0Z_ISiL729w)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ondrej-kvasnovsky-2.gitbook.io/algorithms/sorting/elementary-sorts.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.