linked list quicksort

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • Baltazar007
    #1

    linked list quicksort

    Does anyone know how to make quicksort for single linked list without
    using array?


    I know that mergesort is maybe better but I need quicksort!!

    thnx
    Tags: None
    • CBFalconer
      #2
      Re: linked list quicksort

      Baltazar007 wrote:
      >
      Does anyone know how to make quicksort for single linked list
      without using array?
      >
      I know that mergesort is maybe better but I need quicksort!!
      Why? Mergesort handles the list in place. Quicksort requires an
      array, and you don't have one unless you create an auxiliary
      array. Total waste.

      --
      Chuck F (cbfalconer at maineline dot net)
      Available for consulting/temporary embedded and systems.
      <http://cbfalconer.home .att.net>

        Comment

        • Ivan Vecerina
          #3
          Re: linked list quicksort

          "Baltazar00 7" <OBRISIOVO_balt azar007@gmail.c omwrote in message
          news:ej4r6d$p9t $1@news2.carnet .hr...
          : Does anyone know how to make quicksort for single linked list without
          : using array?
          :
          : I know that mergesort is maybe better but I need quicksort!!

          MergeSort is not maybe better, it is guaranteed to be (as good)
          or better than QuickSort when sorting a linked list.

          QuickSort requires random access to the elements that are to
          be sorted, which make it very unsuitable for a linked list.

          What makes you say that you "need" QuickSort ?


          Ivan
          --
          http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

            Comment

            • Eric Sosman
              #4
              Re: linked list quicksort

              Ivan Vecerina wrote:
              "Baltazar00 7" <OBRISIOVO_balt azar007@gmail.c omwrote in message
              news:ej4r6d$p9t $1@news2.carnet .hr...
              : Does anyone know how to make quicksort for single linked list without
              : using array?
              :
              : I know that mergesort is maybe better but I need quicksort!!
              >
              MergeSort is not maybe better, it is guaranteed to be (as good)
              or better than QuickSort when sorting a linked list.
              >
              QuickSort requires random access to the elements that are to
              be sorted, which make it very unsuitable for a linked list.
              Quicksort does not "require" random access. Pluck the first
              node from the list and call it the partitioning element, walk
              sequentially through the list reassigning its nodes to two new
              lists depending on how they compare to the partitioning node (if
              desired, make a third list for nodes that compare equal), sort
              the two lists recursively, and concatenate.

              Unfortunately, it seems difficult to avoid degeneracy in a
              way that's both effective and cheap. Choosing the first node as
              the partioning element is cheap, but runs a substantial risk of
              degeneracy: for example, if the list is already in order or in
              reverse order, each partitioning pass accomplishes almost nothing.
              You could choose a "random" node from a list of known length at the
              cost of generating one random number and traversing (on the average)
              half the list before each partitioning pass, or you could make the
              choice while building the list at the cost of generating a random
              number for each node added. Neither of these strategies seems cheap.
              What makes you say that you "need" QuickSort ?
              His teacher, I bet.

              --
              Eric Sosman
              esosman@acm-dot-org.invalid

                Comment

                • Skybuck Flying
                  #5
                  Re: linked list quicksort


                  "Baltazar00 7" <OBRISIOVO_balt azar007@gmail.c omwrote in message
                  news:ej4r6d$p9t $1@news2.carnet .hr...
                  Does anyone know how to make quicksort for single linked list without
                  using array?
                  >
                  >
                  I know that mergesort is maybe better but I need quicksort!!
                  >
                  thnx
                  Quicksort on double linked list is possible

                  Quicksort on single linked list ? I dont know, maybe it's possible.

                  Dirtysort would be a better name.

                  Unlucky pivot = crash and burn ;)

                  Bye,
                  Skybuck.





                    Comment

                    • Baltazar007
                      #6
                      Re: linked list quicksort

                      Ivan Vecerina wrote:
                      "Baltazar00 7" <OBRISIOVO_balt azar007@gmail.c omwrote in message
                      news:ej4r6d$p9t $1@news2.carnet .hr...
                      : Does anyone know how to make quicksort for single linked list without
                      : using array?
                      :
                      : I know that mergesort is maybe better but I need quicksort!!
                      >
                      MergeSort is not maybe better, it is guaranteed to be (as good)
                      or better than QuickSort when sorting a linked list.
                      >
                      QuickSort requires random access to the elements that are to
                      be sorted, which make it very unsuitable for a linked list.
                      >
                      What makes you say that you "need" QuickSort ?
                      >
                      >
                      Ivan

                      I need it for homework

                        Comment

                        • Flash Gordon
                          #7
                          Re: linked list quicksort

                          Baltazar007 wrote:

                          <snip>
                          I need it for homework
                          In that case don't you think it would be a good idea to at least make
                          some kind of attempt?

                          I would also point out that the best solution in C often is not good C++
                          and the best solution in C++ often is not C, so cross-posting between
                          comp.lang.c and comp.lang.c++ is rarely a good idea. I'll also bet your
                          teacher specified which language to use and you won't get very good
                          marks if you use the wrong one.
                          --
                          Flash Gordon

                            Comment

                            Previous template Next
                            Working...