CODEWITHSUNDEEP
algorithmsortingdata-structures
tim
tim

Reputation: 31

how to sort data at the time of adding it, not later?

I am new to algorithms so please forgive me if this sounds basic or stupid.

I want to know this : instead of adding data into some kind of list and then performing a sort on the list, is there a method (data structure+algorithm) that lets me sort the data at the time of adding itself, or to put it another way, inserts the data in its proper place?

eg: if I want to add '3' to {1,5,6}, instead of adding it at the start or end and then sorting the list, I want '3' to go after '1' "directly".

thanks

Upvotes: 3

Views: 442

Answers (5)

Arjun Bhandage
Arjun Bhandage

Reputation: 11

Here is a golang code that sorts inputs on the fly

What I am doing here is that I am determining the position of where possibly the input will fit through binary search and then partitioning the already sorted array to fit the element, appending to part one and then rejoining the two parts.

time complexity = Log N(to determine the position) + 3N (to create slices and append for each input)

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    var a []int
    for {
        fmt.Print("Please enter a value:")
        text := readLine(reader)
        key, _ := strconv.ParseInt(text, 10, 0)
        pos := binarySearch(a, 0, len(a)-1, int(key))
        p1 := append([]int{}, a[:pos]...)
        p2 := a[pos:]
        p1 = append(p1, int(key))
        p1 = append(p1, p2...)
        a = p1
        fmt.Println(a)
    }
}

func binarySearch(a []int, low int, high int, key int) int {
    var result int
    if high == -1 {
        return 0
    } else if key >= a[high] {
        return high + 1
    } else if key <= a[low] {
        return low
    }
    mid := (high + low) / 2
    if a[mid] == key {
        result = mid
    } else if key < a[mid] {
        return binarySearch(a, low, mid-1, key)
    } else if key > a[mid] {
        return binarySearch(a, mid+1, high, key)
    }
    return result
}

func readLine(reader *bufio.Reader) string {
    text, err := reader.ReadString('\n')
    if err != nil {
        fmt.Println(err)
    }
    text = strings.TrimRight(text, "\n")
    return text
}

Upvotes: 0

Landei
Landei

Reputation: 54584

If you use a binary search tree instead of an array, the sorting would happen "automatically", because it's already done by the insert method of the nodes. So a binary tree is always sorted, and it's easy to traverse. The only problem is that when you have already (more or less) sorted data, the tree becomes inbalanced (which is where red-black-trees and other variations come into play).

Upvotes: 8

Aaron Digulla
Aaron Digulla

Reputation: 328624

Yes but that's usually slower than adding all the data and sorting it afterwards because to insert the data as it is added, you need to traverse the list every time you add an element.

With binary search, you need not look at every element but even then, you often need to get more elements from the list as when you sort afterwards.

So from a performance view, sorted insert is inferior to post sorting.

Upvotes: 0

Guffa
Guffa

Reputation: 700382

There are basically two different methods to insert a value in a list, which you use depend a bit on what kind of list you are using:

  • Use binary search to locate where the value should be inserted, and insert the value there.

  • Loop from the end of the list, moving all higher values one step up, and put the value in the gap before the lowest higher value.

The first method would typically be used if you are using a binary tree or a linked list, where you don't have to move items in the list to do the insert.

Upvotes: 0

Xion
Xion

Reputation: 22770

You want to maintain a sorted array at all times, so you shall find a correct place in sequence for every new element you want to add to the array. This can be done efficiently (O(logn) complexity) by utilizing a modified binary search algorithm.

Upvotes: 1

Related Questions